第1期 王立敏等：基于最小社团链接度增量的社团结构挖掘算法 ,117, [5]Radicchi F.Castellano C.Cecconi F,et al.Defining and identify- 4结论 ing communities in networks.Proc Natl Acad Sci USA,2004. 101(9):2658 尽管目前有许多关于挖掘网络社团结构的算 [6]Girvan M.New man M E J.Community structure in social and 法，但是这些算法都需要知道网络的整体结构，而对 biological networks.Proe Natl Acad Sci USA,2002.99(2): 于规模庞大而且不断变化的网络（例如万维网）很难 7821 充分了解它的整体结构，此外，在实际应用中，在某 [7]Newman M E J.Mixing patterns in networks.Phys Reo E. 些情况下只是想了解网络的局部社团结构，本文提 2003,67(2):026126 出衡量局部社团结构的数量化指标一局部社团外 [8]Duch J.Arenas A.Community detection in complex networks us- ing extreme optimization.Phys Rev E.2005.72(2):027104 部链接度，以及给出一种挖掘局部社团结构的算法， [9]Wang X T,Chen G R.Lu HT.A very fast algorithm for detect- 可以很好地解决上述问题，本算法的时间复杂度为 ing community structures in complex networks.Phys A.2007. O(kd),其中d为网络的平均节点度数，k为社团 384(2):667 成员数；但搜索社团成员的正确率较Clauset算法略差 [10]Clsuet A.Newman M E J.Cristopher M.Finding community structure in very large network.Phys Rev E.2004.70(6): 066111 参考文献 [11]Xu X W,Yuruk N.Feng Z D,et al.Scan:a structural cluster- [1]Spirin V,Mirny L A.Protein complexes and functional modules ing algorithm for networks/Proceedings of the 13th ACM in molecular networks.Proc Natl Acad Sci USA,2003,100 SIGKDD international Conference on Know ledge Discovery and (21):12123 Data Mining-New York:KDD '07 ACM.2007:824.DOI [2]Newman M E J.Girvan M.Finding and evaluating community =http:∥doi~acm-org/10.1145/1281192.1281280 structure in network.Phys Rev E.2004.69(2):026113 [12]Bagrow JP.Bollt E M.A local method for detecting communi- [3]Wilkinson D M.Huberman B A.A method for finding communi- ties.Phys Rev E,2005,72(4):046108 ty of related genes.Proc Natl Acad Sci USA,2004,101 (Suppl [13]Clauset A.Finding local community structure in networks.Phys 1):5241 RewE,2005,72(2):026132 [4]Gieiser P,Danon L.Community structure in jazz.Ade Complex [14]Zachary WW.An information flow model for conflict and fission S,2003,6(4):565 in small group.JAnthropol Res,1977.33(4):4524 结论 尽管目前有许多关于挖掘网络社团结构的算 法‚但是这些算法都需要知道网络的整体结构‚而对 于规模庞大而且不断变化的网络（例如万维网）很难 充分了解它的整体结构．此外‚在实际应用中‚在某 些情况下只是想了解网络的局部社团结构．本文提 出衡量局部社团结构的数量化指标———局部社团外 部链接度‚以及给出一种挖掘局部社团结构的算法‚ 可以很好地解决上述问题．本算法的时间复杂度为 O（ kd）‚其中 d 为网络的平均节点度数‚k 为社团 成员数；但搜索社团成员的正确率较Clauset 算法略差． 参 考 文 献 ［1］ Spirin V‚Mirny L A．Protein complexes and functional modules in molecular networks．Proc Natl Acad Sci USA‚2003‚100 （21）：12123 ［2］ Newman M E J‚Girvan M．Finding and evaluating community structure in network．Phys Rev E‚2004‚69（2）：026113 ［3］ Wilkinson D M‚Huberman B A．A method for finding communi￾ty of related genes．Proc Natl Acad Sci USA‚2004‚101（Suppl 1）：5241 ［4］ Gieiser P‚Danon L．Community structure in jazz．A dv Complex Syst‚2003‚6（4）：565 ［5］ Radicchi F‚Castellano C‚Cecconi F‚et al．Defining and identify￾ing communities in networks．Proc Natl Acad Sci USA‚2004‚ 101（9）：2658 ［6］ Girvan M‚Newman M E J．Community structure in social and biological networks．Proc Natl Acad Sci USA‚2002‚99（2）： 7821 ［7］ Newman M E J．Mixing patterns in networks．Phys Rev E‚ 2003‚67（2）：026126 ［8］ Duch J‚Arenas A．Community detection in complex networks us￾ing extreme optimization．Phys Rev E‚2005‚72（2）：027104 ［9］ Wang X T‚Chen G R‚Lu H T．A very fast algorithm for detect￾ing community structures in complex networks．Phys A‚2007‚ 384（2）：667 ［10］ Clsuet A‚Newman M E J‚Cristopher M．Finding community structure in very large network．Phys Rev E‚2004‚70（6）： 066111 ［11］ Xu X W‚Yuruk N‚Feng Z D‚et al．Scan：a structural cluster￾ing algorithm for networks ∥ Proceedings of the 13th ACM SIGKDD international Conference on Knowledge Discovery and Data Mining．New York：KDD ’07ACM‚2007：824．DOI ＝http：∥doi．acm．org／10．1145／1281192．1281280 ［12］ Bagrow J P‚Bollt E M．A local method for detecting communi￾ties．Phys Rev E‚2005‚72（4）：046108 ［13］ Clauset A．Finding local community structure in networks．Phys Rev E‚2005‚72（2）：026132 ［14］ Zachary W W．An information flow model for conflict and fission in small group．J A nthropol Res‚1977‚33（4）：452 第1期 王立敏等： 基于最小社团链接度增量的社团结构挖掘算法 ·117·