社交网络中FN算法结果的后处理研究

doi:10.11896/j.issn.1002-137X.2015.06.054

摘要/Abstract

摘要： 在复杂网络问题的研究中,众多聚类算法的横向比较与改进研究方面的工作在近几年吸引了大量注意并得到深入研究。其中,基于模块度的算法被广泛应用,而模块度也作为评价聚类的一项指标。在这类算法中,基于模块度的快速Newman算法(Fast-Newman algorithm,FN)显得较为突出,许多相关的深入研究由此展开,但多数工作是基于算子改进、应用领域等方向展开的,而对于算法结果的研究工作则更多偏向于评价、测量和总结。该研究从FN算法的结果入手,对算法的分类结果进行数据的后处理。在研究中发现了FN算法中常见的错误类型,并提出了3种不同的解决方案,使得最终结果更加符合实际,达到更好的聚类效果。在部分案例中准确率可提高至100%。

关键词: 社团挖掘,FN算法,后处理,复杂网络,社交网络

Abstract: During the last few years,the clustering algorithms’ transverse comparison in the field of complex networks has attracted a lot of attention.Among them,the algorithm based on modularity is widely used,and modularity is viewed as an evaluation for a clustering.The Newman fast algorithm based on the modularity (Fast-Newman algorithm,FN for short) is more prominent.Many related researches are based on the FN algorithm,however,most of the works focus on operator improvement,application field extension,etc.For the results of the FN algorithm,most of research works are tend to evaluation,measure and summarize.The study focuses on the post-processing of the classification results of the FN algorithm.The research shows the common feature of the error nodes in the FN algorithm,and proposes three different solutions to make the final results more correspond to the actual situation and achieve a better clustering result.In some cases,the clustering accuracy is up to 100%.

Key words: Community mining,FN algorithm,Post-processing,Complex network,Social network

倪涵,白清源. 社交网络中FN算法结果的后处理研究[J]. 计算机科学, 2015, 42(6): 256-261. https://doi.org/10.11896/j.issn.1002-137X.2015.06.054

NI Han and BAI Qing-yuan. Research of Post-processing of FN Algorithm Results in Social Networking[J]. Computer Science, 2015, 42(6): 256-261. https://doi.org/10.11896/j.issn.1002-137X.2015.06.054

参考文献

[1] Xie Zhou,Wang Xiao-fan.An Overview of Algorithms for Analyzing Community Structure in Complex Networks[J].Complex Systems and Complexity Science,2005,2(3):1-12
[2] Gibson D,Kleinberg J,Raghavan P.Inferring web communities from link topology [C]∥Proceedings of the 9th ACM Confe-rence on Hypertext and Hypermedia.1998:225-234
[3] Flake G W,Lawrence S R,Giles C L,et al.Self organization and identification of web communities [J].IEEE Computer,2002,35(3):66-71
[4] Adamic A L,Adar E.Friends and neighbors on the Web[J].Social Networks,2003,25(3):211-130
[5] Shen-Orr S,Milo R,Mangan S,et al.Network motifs in thetranscriptional regulation network of Escherichia coli [J].Nature Genetics,2002,31(1):64-68
[6] Milo R,Shen-Orr S,Itzkovitz S,et al.Network motifs:simplebuilding blocks of complex networks [J].Science,2002,298(5594):824-827
[7] Holme P,Huss M,Jeong H.Sub network hierarchies of biochemical path ways[J].Bioinformatics,2003,19(4):532-538
[8] Girvan M,Newman M E J.Community structure in social and biological networks[J].Proc Natl Acad Sci,2001,99(12):7821-7826
[9] Gleiser P,Danon L.Community structure in jazz[J].Advances in Complex Systems,2003,6(4):565-573
[10] Garey M R,John son D S.Computers and Intractability:A Guide to the Theory of NP-Completeness [M].San Francisco:W.H.Freeman Publishers,1979
[11] Scott J.Social Network Analysis:A Handbook(2nd ed)[M].London:Sage Publications,2002
[12] Wang Xiao-fan,Liu Ya-bing.Overview of Algorithms for Detecting Community Structure in Complex Networks[J].Journal of Electronic Science and Technology Photonic Sensors,2009,38(5):537-543
[13] Newman M E J.Random graphs with clustering [J].Phys Rev Lett,2009,103:058701
[14] Newman M E J.Detecting community structure in networks[J].Eur Phys J B,2004,38(2):321
[15] Sales-Pardo M R,Guimera A,Moreira A,et al.Extracting the hierarchical organization of complex systems [J].Proc Natl Acad Sci USA,2007,104:15224
[16] Blondel V D,Guillaume J L,Lambiotte R,et al.Fast unfolding of community hierarchies in large networks [J].Journal of Statistical Mechanics:Theory and Experiment,2008,10:10008
[17] Shen H,Cheng X,Cai K,et al.Detect overlapping and hierarchical community structure in networks [J].Physica A,2009,388:1706-1712
[18] Zhang S,Wang R S,Zhang X S.Identification of overlappingcommunity structure in complex networks using fuzzy c-means clustering [J].Physica A,2007,374:483-490
[19] Zhang S,Wang R S,Zhang X S.Uncovering fuzzy communitystructure in complex networks [J].Phys Rev E,2007,76(4):046103
[20] Newman M E J,Girvan M.Finding and evaluating communitystructure in networks [J].Phys Rev E,2004,69(2):026113
[21] Newman M E J.Fast algorithm for detecting community structure in networks[J].Phys Rev EstatNonlin Soft Matter Phys,2004,9(6):06133
[22] Kernighan B W,Lin S.A efficient heuristic procedure for partitioning graphs [J].Bell System Technical Journal,1970,49(2):291-307
[23] Fiedler M.Algebraic connectivity of graphs [J].Czech Math J,1973,23(98):298-305
[24] Pothen A,Simon H,Liou K-P.Partitioning sparse matrices with eigenvectors of graphs [J].SIAM J Matrix Anal Appl,1990,1(3):430-452
[25] Zachary W W.An information flow model for conflict and fission in small groups[J].Journal of Anthropological Research,1977,33:452-473
[26] Michael J H.Labor dispute reconciliation in a forest products manufacturing facility[J].Forest Products Journal,1997,47:41-45
[27] Lusseau D.The emergent properties of a dolphin social network[J].The Royal Society,2003,0(Suppl):186-188

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed