复杂网络中的邻域重叠社团结构探测.pdf

} 蒸 可靠传输ReliableTransmission 复杂网络中的邻域重叠社团结构探测 马 磊 (华东师范大学，上海 200241) 摘 要：网络，数学家们称其为图，它为许多复杂系统的结构提供了一个很好的抽象，从社会网络、计算机网络，到生物 网络 以及物理系统的状态空间。在过去的几十年里出现了许多确定网络系统拓扑结构的改进实验，但对实验产生的数据进行 科学的分析，仍然存在本质的挑战。目前的社团检测中主要存在两个问题：一是不知道网络中有几个社团；二是网络中的顶点 可能属于不同的社团，也就是社团中存在重叠结构。为了了解各种重叠社团检测算法的思想、实现步骤、优缺点比较、算法应 用，文中对邻域重叠社团检测算法进行了深入的分析，Vlk-means算法分析了经济网络，同时采用Silhouette指标解决了最佳聚 类数的问题，并通过仿真实验证明了此算法的可能性。 关键词：网络；社团结构；重叠社团；社团检测 中图分类号 ：TP391 文献标识码 ：A 文章编号 ：2095—1302(2012)07·0056—06 Overlappingcommunitystructuredetectionincomplexnetworks MA Lei (EastChinaNormalUniversity，Shanghm200241，China) Abstract：Networks，alsocalledgraphsbymathematicians，provideausefulabstractionofthestructureofmanycomplexsystems，rang— ingfrom socialsystemsandcomputernetworkstobiologicalnetworksandthestatespacesofphysicalsystems．Inhtepastdecades，therehave beensignificantadvna cesinexperimentstodeterminethetopologicalstructureofnetworkedsystems，buthtereremainsubstnatialchallenges inextractingscientificunderstnadingfrom thelargequantfiiesofdataproducedbytheexperiments．Thereraetwomaindifficultiesindetecting communitysturcture．Thefirstisthatitisnotknownthathow manycommunitiesthere areinagivennetwork．Secondly,itisacommoncase thatsomenodesni anetworkcanbelongtomorethanonecommunity．Thismeanstheoverlappingocmmunitysturcturenicomplexnetworks．A newmethodfordetemr iningoptimalnumberofclustersinK-mena sclusteringalgorithm ispresentedtoanalyzehteeconomicalnetwork，select- nigtheSilhouettevalidiyt indexandsettinginitialclusteringcentersbasedonmaximum andminimum distancealgorithm．Simulationexperi— mentnadanalysisdemonstratehtefeasibiliytofhteabove—mentionedalgorithm． Keywords：network；communityst