大型复杂网络中的社区结构发现算法.pdf—92—大型复杂网络中的社区结构发现算法胡健1，董跃华1，杨炳儒2(1.江西理工大学信息工程学院，赣州341010；2.北京科技大学信息工程学院，北京101083)摘要：在大型复杂网络中自动搜寻或发现社区具有重要的实际应用价值。该文把超图模型以及基于此的聚类算法应用到社区结构发现的领域。对于简单图的社区结构发现，引入边聚集系数的概念，提出基于边聚集系数的社区发现算法。将安然邮件数据集作为测试数据集，通过算法对比分析，证明该算法在时间复杂度上可以提高一个数量级。关键词：边聚集系数；社区结构；社区发现CommunityStructureDiscoveryAlgorithminLargeandComplexNetworkHU激an1,DONGYue-hua1,YANGBing-ru2(1.FacultyofInformationEngineering,激angxiUniversityofScienceandTechnology,Ganzhou341010;2.SchoolofInformationEngineering,UniversityofScienceandTechnologyBei激ng,Bei激ng101083)Theautomaticsearchandcommunitydiscoveryinlargeandcomplexnetworkhasimportantpracticalapplications.Thispaperappliesthehypergraphbasedmodelandclusteralgorithmincommunitystructurediscovery,introducestheconceptofEdgeClusteringCoefficient(ECC)tocommunitystructurediscoveryofsimplegraphandproposesanalgorithmofcommunitydiscoverybasedonECC.Enrone-maildatasetsaretestdatasets,throughcomparativeanalysisofalgorithm,toprovethatthisalgorithmcansignificantlyimprovethetimecomplexity.EdgeClusteringCoefficient(EBB);communitystructure;communitydiscovery计算机工程ComputerEngineering第34卷第19期Vol.34No.192022年10月October2022·网络与通信·：1010—3428(2022)19—0092—02文献标识码：A：TP301.61概述复杂网络中社区发现(communityfinding)的研究起源于社会学的研究工作。能够在大型复杂网络中自动搜寻或发现“社区”具有重要的实际应用价值[1]，如社会网络中的社区可能代表的是根据兴趣或背景而形成的真实的社会团体，引文网络中的社区或许代表的是针对同一主题的相关论文，万维网中的社区或许就是讨论相关主题的若干网站，而生物化学网络或者电子电路网络中的社区可能就是某一类功能单元。发现这些网络中的社区有助于更有效地理解和开发这些网络。与社区发现相关的成熟理论包括图论以及模式识别。Wu和Huberman的研究成果[2]以及Newman和Girvan的研究成果[3]使得复杂网络中的社区发现成为近几年复杂网络领域的一个研究热点并形成了复杂网络中的一个重要研究方向。Newman和Girvan把社区发现问题定义为将网络节点划分成若干组，使得组内的节点之间连接比较稠密而不同组节点之间的连接则比较稀少。Newman和Girvan在其研究中提出了基于边介数(edgebetweenness)概念的分割方法，尽管该方法计算量很大，但由于其性能优越而成为社区发现研究的重要参考模型。对于一般简单图的社区发现，也可以称之为基于图的聚类，把具有相同或者相似属性的有共性的节点聚合到一起，形成一个个的聚类[2]。这方面的方法有很多，最常用的有G-N算法、谱二分法和层次聚类法。尽管人们对复杂网络的社区发现问题已进行了大量的研究，但是仍然存在一些目前无法解决的基本问题[4]，如社区的概念虽然大量使用，但却缺少严格的数学定义；大多数社区发现算法虽然性能优越，但所需要的计算量却很大；更为关键的是，很多算法不是针对异构数据集。这说明复杂网络中社区发现的研究还远没有成为体系，还有很多工作待完善。2边的聚集系数定义为了刻画描述一个网络，通常有这样几个角度，一个是这个网络中点与点之间的距离以及整个网络的平均距离；另一个是每个节点的度以及整个网络的平均的度；还一个就是节点之间聚集的情况，点的聚集系数这个概念是用来体现对于某个节点A来讲，如果B和C都是A的邻接点(朋友关系)，那么B和C两者之间也有邻接(朋友)的可能性。定义1某节点n的聚集系数(nodeclusteringcoefficient)()Cn如下定义：(1)假设某节点n的度是k，则该节点的这些邻居之间可能形成边的最大数是：()(1)/2Tnkk=?(2)()En表示图中这些邻居之间实际的...