Computer Science ›› 2015, Vol. 42 ›› Issue (6): 256-261.doi: 10.11896/j.issn.1002-137X.2015.06.054

Previous Articles     Next Articles

Research of Post-processing of FN Algorithm Results in Social Networking

NI Han and BAI Qing-yuan   

  • Online:2018-11-14 Published:2018-11-14

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

[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

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!