复杂性工业共生网络的社团结构划分

针对复杂性工业共生网络难以实现定量区域划分的现状,应用复杂网络理论中社团划分算法,提出对复杂性工业共生网络进行定量区域划分的方法,同时针对复杂性工业共生网络社团结构特点,在Grirvan-Newman模块度以及连接密度和内聚系数的基础上,提出一种对复杂性工业共生网络社团划分结果的评价方法,此方法不受复杂性工业共生网络分辨率的限制,当网络中社团大小差异较大时仍然适用。以锦界生态园为例,应用Capocci谱平分法对其网络结构进行了社团划分,采用所提出的评价方法对划分结果进行了评价,验证了复杂性工业共生网络社团划分结果的评价方法。结果表明,采用复杂网络理论中社团划分算法对复杂性工业共生网络的定量区域划分是可行的。     

2种社团发现算法对工业共生网络演化过程描述的比较

针对工业共生网络特点,分别应用改进后的谱平分算法和凝聚算法2种典型的社团发现算法对卡伦堡及鲁北工业共生网络进行社团划分,并对其集聚性程度进行定量的比较和评价,从而对卡伦堡及鲁北工业共生网络演化过程做出定量描述,并与其实际工业共生网络的演化发展过程做出对比。结果表明,采用复杂网络社团划分算法可以实现对工业共生网络发展演化过程的定量描述,而改进后的谱平分算法比凝聚算法对工业共生网络演化过程的描述更接近其实际的发展状况。     

三种经典复杂网络社区结构划分算法研究

社团结构是复杂网络的重要特征之一。针对复杂网络中社团划分问题,文章给出了三种经典的社团划分算法,阐述了各种算法的基本原理,并对各算法进行了适当的分析和比较,为实际应用中社团划分算法的选择提供了参考。     

一种基于聚集系数的局部社团划分算法

社团划分算法是复杂网络研究中的一个热点问题.传统的复杂网络社团划分算法都必须获得全局网络的信息.随着网络规模不断增大,获得全局信息的难度随之增加;而在很多情况下只关心网络中某节点所在的局部社团.为了准确、快速地找到大规模复杂网络中的局部社团,提出了一种基于节点聚集系数性质的局部社团划分算法.该算法根据节点的连接频度,利用节点聚集系数的性质,从网络中某一待求节点开始,通过搜索邻居节点,划分该节点的社团结构.该算法只需要了解与待求节点相关的局部网络信息,在解决局部社团划分问题时其时间复杂度比传统的社团划分算法低.同时,该算法也可以应用于复杂网络全局社团结构的划分.利用该算法分别对Zachary空手道俱乐部网络和由Java开发工具包构成的软件网络图进行社团划分实验,并且分别对实验结果与对象网络的具体特征进行了对比分析.     

MSNV:基于多层次社团划分的网络结构可视化方法

针对大规模网络节点数目庞大、结构复杂性高,有限的屏幕空间难以展示其结构特征的问题,提出了一种基于社团划分的多层次网络可视化方法。首先,使用基于网络模块度的社团划分算法对网络节点进行划分,并采用贪婪算法寻找最大模块度的社团划分,得到不同层次粒度的社团;其次,通过设置层次约束力以改进经典力导引算法(FDA),使改进的算法能对不同层次粒度的社团实现分层布局,解决FDA无法展示网络节点层次性的问题;最后,使用多窗口视图、Overview+Detail等交互方法分别展示高层社团和底层节点,实现兼顾网络高层次宏观结构和低层次局部细节的显示。仿真实验中,该算法的社团划分相较于自包含GN算法在效率和准确率上有所提高。案例分析表明,所提方法在大规模网络结构的显示和交互方面具有良好的效果和性能。     

基于最大生成树的社团划分算法

针对层次聚类算法存在复杂度高、准确度低等问题,提出了一种基于最大生成树的社团划分算法。该算法重新定义了节点间相似度,并利用最大生成树进行初始聚类,然后根据社团相似度合并局部社团得到最终划分结果。算法不仅降低了时间复杂度,而且在划分社团的准确度方面有所提高。将该方法在真实网络与人工网络上进行验证和比对,实验结果表明基于最大生成树的社团划分算法能够快速、准确地划分出网络中的社团结构。     

改进的基于局部模块度的社团划分算法

针对大多复杂网络社团划分算法不能快速发现最优节点加入社团的问题,提出一种利用节点亲密度的局部社团划分算法。引入节点亲密度的概念量化社团与邻居节点的关系,按照节点亲密度由大到小选择节点加入社团,最后以局部模块度为指标终止局部社团扩展。在真实网络和人工仿真网络进行实验,并与基于信息压缩的随机游走算法等4种典型社团划分算法相比较,所提算法划分结果的综合评价指标(F1score)和标准化互信息(NMI)均好于比较算法。实验研究表明,所提算法具有较好的时间效率和准确度,适用于大规模网络社团划分。     

基于信息熵的复杂网络社团划分建模和验证

社团结构是复杂网络最普遍和最重要的拓扑属性之一,社团结构的划分方法对分析复杂网络相关统计特性具有十分重要的理论意义.为了提高社团划分精度,提出了一种新的基于信息熵(information entropy)模块度的社团划分算法(简称IE算法).在有着确定社团结构的数据集和不确定社团结构的数据集上,通过选取Q值、社团划分个数、社团最大连通分量大小和强弱社团个数比例4个重要参数,将IE算法与两种最主要的基于模块度的划分算法GN(Girvan-Newman)和FastGN(Fast Girvan-Newman)进行对比,实验结果证明了IE算法在社团划分性能上优于GN和FastGN;将IE和其他7种最主要的经典社团算法进行时间复杂度分析,并在随机网络和真实网络上进行实验,结果表明该算法时间复杂度在GN与FastGN之间,时间复杂度小于GN而精确度优于GN,证明了在大多数数据集上IE算法的社团划分准确度优于传统基于点边比率的社团划分算法的准确度.     

基于相似度指标的社团划分算法

为快速准确地找到复杂网络的社团划分结果,引入相似度指标,提出一种改进的社团划分算法。将网络节点拓扑结构信息作为节点的多维属性,在不改变网络连边的情况下,使输入网络转换为节点多属性网络,并定义节点之间的混合相似度与社团相似度,运用层次聚类思想得到最终的社团划分结果。在真实网络、计算机生成网络上的实验结果表明,该算法能够发现明显的社团结构,并且具有较高的社团划分准确率。     

基于拓扑特征的二分网络社团结构划分

目前社团结构划分算法只能划分1类节点并且依赖于额外参数。为此,在分析二分网络社团拓扑特征的基础上,利用社团核与外层的思想,提出一种新的社团结构划分算法。该算法完全依赖于原始网络本身的拓扑结构,并且允许社团间重叠。实验结果表明,该算法无需任何额外参数,即可比较准确地识别实际网络的社团个数,同时划分2类节点的社团结构。     

一种基于超网络视角的复杂网络社团区划算法

社团结构是复杂网络最普遍和最重要的属性之一, 复杂网络的社团区划研究就是要合理地划分出复杂网络中真实存在的社团结构。主要将超网络的思想及理论方法应用于复杂网络的社团区划研究, 针对当前GN算法的一些不足, 从超网络视角出发, 结合标准化程度中心性理论方法, 构建了一种新的复杂网络社团区划算法, 通过算例对新算法进行了验证与分析。实验结果表明, 与GN算法相比, 新算法在区划结果上有所改进和完善。     

一种面向度中心性及重叠网络社区的发现算法

针对社会网络中存在较多以度中心节点为中心并且具有多社区重叠节点的网络社区结构,提出了一种面向度中心性及重叠网络社区的两阶段发现算法。第一阶段发现初始社区:选取度最大的Top-k个节点作为候选中心节点,并将每个节点与其邻居节点形成候选初始社区,其中如果某候选社区与已形成的初始社区的重叠度低于阈值,则形成一个新的初始社区;第二阶段调整社区划分:通过偏离度机制进行调整,将偏离度最大值对应的节点划分到连接紧密的相应社区内,形成最终社区划分。实验表明,该方法不仅能够揭示网络中以某个节点为中心的密集的社区结构,还能有效处理初始社区不同程度的重叠问题。相比现有算法,所提方法对预先输入的候选初始社区数k值不敏感,并具有较高的准确性和灵活性。     

复杂网络重叠社区结构发现的演化算法研究

复杂网络重叠社区结构的划分已成为复杂网络研究的一个热点,目前已提出了很多关于社区结构发现的算法。提出了一种基于个体从众的演化算法ICEA,基本思想是由节点邻居组成的个体依概率进行从众和变异操作,用较短时间找到最优(或拟最优)模块度的社区划分,社区结构确定后利用邻居投票机制NV发现网络的重叠节点,完成重叠社区的划分。在真实网络的实验结果表明,此算法的使用时间和划分结果都优于典型算法。     

一个基于中心度的社团结构发现新算法*

针对GN算法在社团结构发现中时间复杂度高等问题,提出一种基于中心度的GN改进算法（DCGN）。该算法根据节点中心度以及节点之间的最短路径首先确定社团结构中心节点集,然后逐步删除社团结构中心节点之间的最大边介数连边,完成社团结构划分。DCGN算法避免了GN算法边介数计算开销大的问题,算法的时间复杂度约为O(cmn),其中c为常数,n为网络成员数,m为网络连边数。将DCGN和GN算法同时应用到Zachary网络及计算机随机生成网络中并进行了比较。实验结果表明,所提出的DCGN算法在运行效率和效果方面较之GN算     

基于节点从属度的加权网络重叠社区划分算法

针对传统社区划分算法忽略现实世界网络特征导致社区划分准确率低的问题,提出了一种基于节点从属度的加权网络重叠社区划分算法。该算法提出加权网络模型,通过模型得到了能刻画出真实网络结构的加权网络;通过网络拓扑结构定义了核心社区,核心社区对社区划分的准确性有着重要作用。该算法计算节点与核心社区间的从属度,并与从属度阈值进行比较进行核心社区扩展,根据扩展模块度优化思想,通过不断地调整从属度阈值直到获得最优的社区结构,完成重叠社区划分。在人工网络数据集和真实世界网络数据集上与已有算法进行实验对比,实验结果验证了所提算法能够准确、有效地检测出重叠社区。     

基于K-means聚类算法的复杂网络社团发现新方法

提出了一种基于K-means聚类算法的复杂网络社团结构划分方法。算法基于Fortunato等人提出的边的信息中心度,定义了节点的关联度,并通过节点关联度矩阵来进行聚类中心的选择和节点聚类,从而将复杂网络划分成k个社团,然后通过模块度来确定网络理想的社团结构。该算法有效地避免了K-means聚类算法对初始化选值敏感性的问题。通过Zachary Karate Club和College Football Network两个经典模型验证了该算法的可行性。     

基于K means聚类算法的复杂网络社团发现新方法*

提出了一种基于Kmeans 聚类算法的复杂网络社团结构划分方法。算法基于Fortunato等人提出的边的信息中心度,定义了节点的关联度,并通过节点关联度矩阵来进行聚类中心的选择和节点聚类,从而将复杂网络划分成k个社团,然后通过模块度来确定网络理想的社团结构。该算法有效地避免了Kmeans 聚类算法对初始化选值敏感性的问题。通过Zachary Karate Club和College Football Network两个经典模型验证了该算法的可行性。     

两种聚类算法在顾客行为分析中的应用比较

分析网络群落划分的GN聚类和模式识别中AP聚类两种算法的设计思想和特点;以图书借阅记录为例构建了顾客聚类的数据集,进行了两种算法的聚类比较。研究表明,两种算法从不同角度揭示了顾客群体的结构特征,GN聚类结果与顾客的宏观特征分类相接近,而AP算法结果反映出顾客需求的分布特征。探讨了算法设计原则对实验结果产生的影响。这些工作可为聚类算法的设计改进和顾客行为的数据挖掘等研究提供一定的参考。     

改进的CNM算法对加权网络社团结构的划分

为了对可以反映网络结构局部重要性质的加权网络进行社团结构划分,延续广泛应用的社团结构分级聚类方法,改进Newman贪婪算法（CNM算法）。算法设计中引入点权和边权,并重新定义新的Q函数计算社团模块度,通过寻找Q函数峰值确定社团划分的最终结果。另外以股票价格波动相关性为加权边建立的加权网络为例进行算法检验,社团划分的结果验证了改进的CNM算法的有效性。与改进的GN算法、极值优化算法等划分效果进行比较分析后发现,改进算法在划分准确性及算法复杂度等方面都有明显的优势。     

虚拟社群结构特征可视化呈现的社会网络布局算法研究

近年来,随着虚拟社区的发展,社会网络可视化软件逐渐走向普通社区成员的面前。然而现今社会网络可视化领域所采用的布局算法普遍与社会网络分析法相脱离,无法呈现社群结构特征。因此,提出凝聚子群布局算法与核心位置布局算法,它们分别以凝聚子群分析结果和成员整体中心度为布局依据,呈现社群子群和成员位置两种社群结构特征,并且依据实际数据给出布局效果。