基于相似度的加权复杂网络社区发现方法

针对加权复杂网络中的社区结构发现问题,本文定义基于权重关系的相似度,并在此基础上定义了节点中心度和归属度,改进GN算法的模块度评价函数,提出一种基于相似度的中心聚类算法(SCC).该算法通过计算节点间的相似度,选取合理的中心度大的节点作为社区中心节点,最后基于节点归属度来聚集从而形成社区;同时,提出了用相似度代替边介数的改进GN算法SGN.通过理论分析,并在数据集上进行实验验证,结果表明SCC算法与WGN算法、SGN算法相比,速度和精度上均有较大改善.同时与I2C算法相比,社区的划分有效性更好.     

基于矩阵运算加速的改进社区发现遗传算法

社区发现算法是复杂网络领域的重要研究工具,然而传统的社区发现遗传算法在大规模网络下存在初始种群质量不佳和运行效率低下的问题。为此,本文提出一种基于矩阵运算加速的改进社区发现遗传算法。针对初始种群质量不佳的问题,提出一种新的初始化算子,采用闭包系数有偏向地选择节点构建高质量初始社区;针对计算效率低下的问题,基于矩阵运算重构了传统社区发现遗传算法各个算子,使得算法能使用GPU加速,提升计算效率。仿真实验结果表明,在不同规模的真实网络和LFR合成网络下,本文算法既能保证良好的划分精度,又展现出较其他主流同类算法更高的计算效率。     

基于向量划分的复杂网络社区结构发现

社区结构是复杂网络最重要的结构特性之一,通过优化模块度来进行社区结构发现是目前使用最为广泛的一类方法.通过将网络看做有向图,模块度矩阵可表示为顶点的有向边向量表示的交叉协方差矩阵,但是该矩阵不是正定的.现有方法通过对该矩阵的进行谱分解,提取大于零的特征根对应的成分,将社区发现问题描述为向量划分问题.本文通过修正交叉协方差矩阵的对角线,使之满足正定性条件,将其表示为顶点向量的内积矩阵.因此,无须对模块度矩阵进行谱分解,甚至无须显式计算顶点的表示向量,就可以将基于模块度的社区发现问题重构为一个向量划分问题.进一步,从向量划分的角度解释了有限分辨率现象的根源,设计了以最大化向量夹角为指导的贪婪算法,该方法比直接优化模块度的方法有更高的异质社区分辨能力.在合成网络和真实网络上分别进行了实验验证,实验结果证实了所提方法的可行性和有效性.     

基于极值优化模块密度的复杂网络社区检测

分析了基于优化模块度检测复杂网络社区结构的算法存在解的限制问题,即不能检测出小于一定内在尺度的社区,并提出了基于极值优化模块密度来检测复杂网络社区结构的启发式算法,通过调整局部极值来优化全局的变量,使算法具有更好的持续搜索和跳出局优解的能力.通过人工网络和现实网络实验分析表明,本文算法用于检测大型网络社区时,具有较高的正确率和效率,即使当网络结构变得很模糊时,算法也能很好地工作.     

基于社团密合度的复杂网络社团发现算法

传统的社团发现算法大多存在划分效果和复杂度相矛盾的问题,为了解决该问题,提出一种新的单社团结构评价标准——社团密合度(group density).在此基础上,设计了一种基于凝聚思想的社团发现算法,该算法通过不断融合小社团,使网络的社团结构向平均社团密合度最大的方向发展,并使用模块度检测算法的划分结果.通过与经典的GN,Fast Newman,LPA等算法对多个数据集进行实验对比,验证了本文算法在获得较好的划分效果的同时具有较低的时间复杂度.     

基于密度峰值和网络嵌入的重叠社区发现

密度峰值是一种基于密度的聚类算法,该算法假设类簇中心点具有较高的密度且被密度较小的节点包围.由于图结构的性质,密度峰值无法直接适用于网络结构,现有的基于密度峰值的社区发现算法大部分是基于图的拓扑结构或者邻接矩阵度量节点近似度,这种方法往往引入较大的计算复杂度.文中结合网络嵌入方法通过低维向量表示网络中的节点信息,提出了...     

复杂网络与软件度量分析

用复杂网络理论研究软件系统的复杂性,选取两款面向对象开源软件框架webwork和spring作为研究对象,无(有)向图节点代表类,边代表类间的依赖和关联等关系,将系统抽象为网络图,并对其拓扑结构进行分析.研究表明:无(有)网络具有较大的聚类系数和较小的平均路径长度,具有小世界特性.由于框架都使用了依赖注入和控制反转,程序中类之间的关系,完全由spring容器来控制,而不是由代码控制,容器运行时会根据spring提供的配置信息注入到组件中.用依赖注入的一个结果是改变了编译阶段部分类之间的相互关系,由原来的关联实体类到关联加载配置文件类,从而影响节点的度包括入度和出度,使无(有)向图的边(弧)数改变.实验结果表明:度分布统计特性仍然具有无标度特性.     

基于注意力网络特征的社区发现算法

现实世界中许多网络都是根据社区结构紧密组织起来的,发现社区对于了解复杂网络的结构及其关系有很大的帮助,文中提出了一种基于注意力网络特征的社区发现(community discovery algorithm based on attention network features,CANF)算法,利用标记节点频率和反示例节...     

异质网络社区发现方法研究综述

社区结构是复杂网络研究中的重要领域,也是复杂网络的重要特征之一,发现网络中的社区结构在理解网络功能方面起着重要作用。通过对国内外异质网络社区发现文献进行深入研究,较为全面地对现有异质网络社区发现算法进行了归纳总结。首先,通过对国内外异质网络社区发现文献进行归纳,给出异质网络社区发现的基本概述,明确异质网络社区发现领域相关问题的基本定义。其次,介绍了异质网络社区发现算法及主要评价指标,利用不同网络结构以及算法对现有方法进行分类概述。最后,对异质网络社区发现算法的发展趋势进行了总结与展望,提出未来可以将研究重点集中在以下几个方面:1)探索基于异质网络的社区发现评价标准,以推动该领域的快速发展;2)设计更加通用的算法模型,解决由先验知识引起的未知社区数量问题;3)开展更多关于动态网络的研究。     

基于大规模复杂网络社区发现的科研合著网络分析

针对基于极大团的社区发现算法,设计了适应大规模数据的MapReduce并行计算框架,提出了基于大规模复杂网络社区发现的科研合著网络分析算法,并用于对我国管理科学与工程领域2012年科研合著网络进行社区结构划分。实验结果表明,基于MapReduce的并行社区发现算法可在保证正确性的同时有效提高计算效率,适用于大规模复杂网络的社区发现。针对我国管理科学与工程领域2012年科研合著网络的社区划分结果展现了我国管理科学与工程领域科研合作的特点和问题。     

动态网络中基于局部介数的重叠社区发现算法

针对现有静态网络社区发现算法的失真和动态网络社区发现算法时间复杂度较高的问题,本文提出了一种动态网络中的重叠社区发现算法。在网络中,边介数最大的边或分割介数最大的节点是网络中的关键边或点,即联系最不紧密的边或节点,因此,该算法利用去除最大边介数的边和分裂最大分割介数的节点的方法,并将网络社区的动态变化和重叠性考虑在内进行社区发现。最后利用模块度对社区发现进行控制,使发现的社区结构更加合理。     

基于复杂网络的城市路网可靠性分析

为分析城市路网中线路的重要程度,采用对偶拓扑方法,将路段抽象为节点,将交叉口抽象为网络边,对实际路网进行拓扑结构转换。应用复杂网络节点度、边介数等特征指标及网络可靠性指标评价城市路网结构特征。最后,分别在蓄意攻击和随机故障条件下,对济南市区路网的连通可靠性进行了实证研究。     

基于量子模糊聚类算法的复杂网络社团结构探测

研究了复杂网络的社团结构特性,探讨了复杂网络的社团结构探测算法.针对现有算法中判断社团结构时的主观性问题,提出了量子模糊聚类算法,并将该算法用于复杂网络社团结构的探测.实验结果表明:该算法可以准确、有效地探测到网络中实际存在的社团结构.     

边介数标准偏差对复杂网络同步能力的表达

通过对各种典型复杂网络的同步能力进行研究,发现一般用来表征网络同步能力的结构参数只适用于部分网络,而边介数标准偏差能够很好地表征网络同步能力,即负载分布均匀性才是影响网络同步能力的主要因素.并指出文献中报道的复杂团簇网中的反常同步现象其实是由于网络负载分布均匀性的破坏而引起的.这项研究将有利于对复杂网络上同步动力学行为...     

一种基于层次化社团结构的复杂网络可视化平台

基于层次化的网络社团结构,提出了一种可以应用于大型复杂网络的可视化方法,并编程实现了交互平台.该平台采用圆环布局,能提供大量的交互功能,使用户从不同层次上查看网络结构信息.平台还实现了重叠节点的找寻,以及社团动态演化等与网络社团分析有密切关系的功能.     

基于模糊均值的细菌群体趋药性复杂网络社团结构发现

复杂网络的社团发现问题是网络数据挖掘中的重要问题之一.利用基于模糊C均值的细菌群体趋药性算法最大化网络的模块度,算法中模糊C均值的初始值由群体细菌取药性算法获得.模糊C均值算法在此基础上发现复杂网络的社团结构.其创新点在于最佳模块度的寻找.实验结果表明:该算法具有对现实世界网络社团划分的可行性和有效性.     

基于复杂网络的市场动力学模型

基于复杂网络理论,建立了具有典型复杂网络结构特征的消费网络模型,及其消费网络模型上的市场动力学模型.从定量描述消费网络上信息传播与消费者企业间行为模式的角度,得到了定量评估广告投入效应的有效方法.     

一种基于广度优先搜索的社区发现方法

由于当前的算法不能很好地将网络的联通性和单个节点的属性综合考虑,分析了凝聚和分裂层次聚类经典算法的局限性,从而给出边的载荷、边的权重、连接度门限、图形分割等定义.综合考虑网络的拓扑结构和边的权重关系,提出了基于广度优先搜索的社会网络社区发现算法SoNetCD.算法通过删除社区之间的边而得到社区结构,它对社区之间的边判断准确,对社区内部的边误删率低.运用经典数据集进行实验的结果表明,该算法具有比经典GN算法更好的结果.