关键词： 高维数据   子空间聚类   稀疏表示   社团检测   复杂网络  

摘要： 现有的子空间聚类方法大多只适用于单层网络,或者仅对多层网络中每层的聚类结果简单地进行平均,未考虑每层网络中包含信息量不同的特点,致使聚类性能受限。针对该问题,提出一种面向多层网络的稀疏子空间聚类方法。将距离正则项和非负约束条件集成到稀疏子空间聚类框架中,从而在聚类时能够同时利用数据的全局信息和局部信息进行图学习。此外,通过引入稀疏约束使学习到的图具有更清晰的聚类结构,并设计迭代算法进行优化求解。在多个真实数据集上的实验结果表明,该方法能够挖掘网络不同层的互补信息,得到准确的一致性联合稀疏表示,有效提高社团聚类性能。

关键词： 社团检测   Python   i-Graph  

摘要： 社团检测是一种技术,通过监督学习、半监督学习、无监督学习或者强化学习将网络中的节点划分为独立的集合。随着互联网的发展,社交软件的普及,这一研究领域得到了重视。社团检测已经拥有了许多经典的算法,这些算法在实际应用中也得到了很好的发挥和效果。目前,半监督学习社团检测相比于监督学习社团检测,学习成本较低,半监督社团检测的发展具有较大的挑战与前景。

关键词： 复杂网络   社团检测   标签传播   核心节点预划分   随机性  

摘要： 标签传播算法是一种典型的社团检测算法,针对已有的社团检测结果不稳定的情况,提出了一个基于循环查找核节点的标签传播算法,减少了标签初始化和选择过程中的随机性.基于核心节点实现网络预划分,利用循环核心节点查找传播标签;在邻居节点的标签存在相同数量情况下,只对核心节点进行赋值标签,其他节点从其靠近的核心节点获取标签.在3个测试网络上的结果表明:本算法可以更为准确的检测出复杂网络的社团结构.

关键词： 复杂网络   社团检测   k最近邻   社团主干  

摘要： 随着复杂网络规模和种类的日渐增加,如何检测任意结构,任意规模的社团成为了社团检测的一个难点.为了解决该问题,提出了一种可以通过k最近邻发现社团主干的社团检测算法DCCB(detection community based on k NN to discover community backbone).该算法首先遍历所有节点,将两个互为k近邻的相似节点及它们的共同邻居聚集到一个社团主干中;接着,在遍历过程中,若不在主干中的节点与某个社团主干内任何节点存在互近邻关系,那么该节点也会被吸引到这个社团主干中;然后,该算法检测出社团主干中的异常节点,并将其标记为无类标节点;最后,该算法利用影响力分配无类标节点,得到最终的社团结构.该算法简单且时间复杂度较低.通过4个不同结构真实网络以及3个不同规模的人工合成网络的综合测试表明:DCCB算法能检测出任意结构与任意规模的社团,且发现的社团质量高于所用的5个基准算法.

关键词： 社团检测   复杂网络   标签传播   网络分析  

摘要： 标签传播算法的社团检测原理简洁、时间复杂性低,产生了大量的基于标签传播的社团检测方法,亟需系统性总结.本文首先分析概括了标签传播算法存在的问题、成因和挑战;然后主要从以下几方面分别阐述了其研究现状,汇总了相关方法采用的策略,分析比较了代表性算法:1)提高算法性能,2)解决不确定性问题,3)解决标签震荡现象,4)解决平凡检测问题,5)重叠社团检测,6)动态社团检测;最后总结了代表性算法的适用场景,并对该类算法的难点和发展趋势进行了展望.

关键词： 复杂网络   社团检测   电网分区   功能性社团结构   拓扑性社团结构  

摘要： 电网分区是运行和保护电网的重要课题。以关联强度代替传统的邻接矩阵,定义电气关联强度(ECS)用来反映电网中任意节点之间的电气特性,并基于发电机节点和负荷节点之间的供电关系提出供电关联强度(PSS)。在经典的模块度(Modularity)基础上,结合供电关联强度提出供电模块度(PS-Modularity)的概念,并基于此对Newman快速算法进行改进,以自动识别供电社团结构。

关键词： 社交网络   社团检测   社团隐私   社团安全   社团隐藏  

摘要： 社团是社交网络的重要特征,社团检测技术的发展给网络用户带来隐私泄露的危险。如何保护敏感的社团信息不被泄露,保障用户与社团安全已经成为网络安全领域的研究热点。近几年,社团保护技术取得了初步进展,但针对社交网络中的社团隐私或社团安全研究进展综述较少,不利于该研究方向的长远发展。因此,主要针对社团结构隐私方面的研究进展进行综述,对最新的相关研究成果进行系统地归纳、总结、比较,并展望了未来的研究方向。

关键词： 社团检测   鲁棒性   攻击方法   增强方法   开源软件  

摘要： 社团结构是存在于许多复杂网络中的一个重要性质。检测网络中的社团结构可以揭示其功能与特点，在社会学、生物学等多个领域有着很大的研究价值。研究社团检测算法的鲁棒性及增强方法，有助于科研工作者对算法进行更加全面的评估，进一步提升社团检测结果的准确性。目前已有的关于社团检测鲁棒性的研究更多关注于恶意攻击对局部检测结果的影响，即目标社团划分错误，较少的研究从全局角度出发，观察遭受攻击后社团检测算法整体的性能下降情况。而在增强方法的相关研究中，已有工作多是通过链路预测相似性指标对网络结构进行调整。如何选取关键节点进行更有效的连边扩充、如何更好地捕获节点间的结构相似性等问题都值得更多的探索。针对上述问题，本文进行了攻击方法和增强方法的研究，并在Apache开源软件数据集上加以应用，具体包括以下三个部分：　　(1)本文从攻击方法的研究入手，观察社团检测算法在遭受恶意攻击时的性能变化，进而评估算法的鲁棒性。特别地，本文从全局角度出发，提出了一种基于遗传算法的Q值攻击方法Q-Attack，针对网络结构特性及攻击目标进行了编码方式和适应度函数的设计。比较Q-Attack与三种启发式攻击方法的攻击效果，实验结果表明Q-Attack能使社团检测算法的性能下降更为明显，同时该方法具有较好的迁移性。观察各社团检测算法在遭受攻击后的性能变化，可以得出，Louvain算法及Infomap算法较实验中其它几种社团检测算法具有更好的鲁棒性。　　(2)不同于研究性能更佳的某种社团检测算法，对增强方法的研究可以通过改善网络结构来提升多种社团检测算法的性能。具体地，本文提出了一种基于关键节点连边扩充的网络增强方法NE-EABC，创新地利用连边的介数中心性进行关键节点的选择，将基于Jaccard相似系数的连边扩充方式和基于重启随机游走采样的连边扩充方式结合，进行网络增强，提升社团检测算法性能。实验结果表明多数情况下NE-EABC较对比方法能表现出更好的增强效果。此外，本文还检验了对抗网络经NE-EABC增强后的社团划分结果质量，结果表明NE-EABC可以改善对抗网络结构，具有一定的防御能力。　　(3)将所提方法应用到Apache开源软件数据集上。本文主要从Apache数据中提取信息构建邮件通讯网络，特别地，考虑到原始数据中不存在开发者标签信息，本文提出了一种开发者邮件通讯网络构建方式，根据开发者所参与的项目补充标签信息，便于使用NMI、ARI指标评估社团检测结果。实验中将攻击方法Q-Attack和增强方法NE-EABC应用于新构建的网络上，进一步验证方法的效果，探究开源软件数据的安全性问题。

关键词： 复杂网络   节点中心性   精准k核   库仑力中心性   标签传播算法  

摘要： 复杂网络是现实世界中复杂系统的抽象模型,它将复杂系统中的实体对象抽象为节点,将实体对象之间的显性或隐性关系抽象为边。节点重要性评估和社团检测作为复杂网络中最热门的两个课题,在计算机、通信、刑侦、社会、金融、交通、生物等诸多领域中得到了广泛的研究与应用。关键节点是构成一个网络并实现其信息传递功能的核心要素,识别关键节点并对其着手保护能够有效提升网络的抗毁性,也能够从关键节点入手提出更高效的网络攻击策略。此外,复杂网络中存在一种特殊的特征结构,社团结构。具体体现在社团内部节点的联系较为紧密,而社团之间的节点联系则相对稀疏,而发现网络中社团结构的过程则称为社团检测。利用社团检测能够轻易地揭示网络中的隐藏结构、反映节点之间的相互关系、分析复杂网络的潜在信息以及预测网络的局部功能特性。本文着手研究了复杂网络中节点重要性评估方法和社团结构检测方法,其主要成果如下:k核是一种常见的节点重要性评估指标,但由于其存在破坏网络整体结构信息、忽略邻居节点影响力等缺点导致每个节点难以量化区分。为了提高关键节点的识别精度,本文首先改进了k核的分解过程,提出了精准k核Ak(Accurate k-shell)。考虑到网络中局部特征信息和全局结构信息对节点的影响,本文随后将精准k核应用到重力中心性GC(Gravity Centrality)中并提出了库仑力中心性CFC(Coulomb Force Centrality)。信息学中的香农熵在网络关键节点识上具有良好的扩展性,通过结合邻域度中心性、邻域精准k核以及库仑力中心性三者的香农熵,最终本文提出了混合中心MC(Mixed Centrality)。该指标能将节点的拓扑结构信息、位置信息、局部特征信息和网络整体拓扑结构信息充分融合,消除单一指标评估节点时产生的片面性,从而达到对节点多元化评估的目的。在7种真实网络下,对MC和其它节点评估指标分别从单调性和准确性上进行了一系列实验,实验结果表明MC具有更好的关键节点识别性能。标签传播算法(LPA)是一种高效快速的社团检测算法,能够适用于不同规模大小的网络。然而,由于标签的随机传播和收敛条件的不明确致使实验结果非常不稳定。为了进一步识别出网络中的关键节点,本文首先在CFC的基础上提出了联合中心性UC(Union Centrality)。随后,针对LPA中节点随机选择标签这一缺陷,本文利用UC设计出了用于量化评估节点标签传播能力的标签选择性LS(Label Selectivity)。通过将UC和LS这两种指标应用到LPA中,本文最终提出了基于库仑力中心性的标签传播算法CFCLPA。该算法消除了原始LPA中的随机性并且明确了算法的结束条件,从而使其具备了高效精确的社团结构识别能力。在真实网络和LFR基准网络下进行了一系列测试和比较,实验结果表明CFCLPA具有更优秀的社团检测性能。

关键词： 社团检测   邻接矩阵   标签传播   非负矩阵分解  

摘要： 在互联网飞速发展的背景下,复杂网络研究已经成为一项热门研究方向。复杂网络中往往存在属性相似或者关系紧密的结点,社团检测方法通过分析复杂网络中结点之间的联系,将结点划分到不同社团,从而得到社团网络结构。社团检测算法分为两类,即非重叠和重叠社团检测算法。传统的非负矩阵分解(Non-negative Matrix Factorization,NMF)算法将网络的邻接矩阵分解,从而得到非重叠社团结构,但邻接矩阵体现的是每个结点与其直接邻居之间的关系,位于同一社团的结点往往并不只是直接邻居关系。本文在NMF研究的基础上,提出了两种算法,非重叠社团检测算法LPNMF(Label Propagation on Non-negative Matrix Factorization),重叠社团检测算法Link NMF(Non-negative Matrix Factorization on Link-graph)。(1)社团检测算法LPNMF:使用标签传播算法对网络进行社团划分,并得到社团的模块度,在标签传播算法得到的社团结构中,如果两个结点属于同一社团,为其在邻接矩阵中的元素值附加模块度的值,来增强这些结点间的关系。因为标签传播算法有着高效率、不稳定的特性,因此通过多次标签传播,快速得到多个社团,加强每次在同一个社团中的结点之间的关系,然后对新的矩阵进行非负矩阵分解,得到网络的最终社团结构。(2)重叠社团检测算法Link NMF:先将网络转化为边图,获得边图的邻接矩阵,与LPNMF算法的思想类似,通过标签传播算法来增加边图的邻接矩阵中属于同一个社团的元素值,再对由边图的邻接矩阵和标签传播算法获得的新矩阵进行非负矩阵分解,得到边的划分结果,最后将边图还原为原始图。在LPNMF检测到的隶属矩阵上,设置阈值参数来过滤掉多余的重叠结点,获得网络的最终重叠社团结构。在多个数据集上与多个算法进行对比实验,结果证明,本文提出的两个算法在非重叠网络和重叠网络上都能得到高质量的社团划分结果。