Computer Science ›› 2020, Vol. 47 ›› Issue (6A): 102-107.doi: 10.11896/JsJkx.190900170

• Artificial Intelligence • Previous Articles     Next Articles

Polynomial Time Community Detection Algorithm Based on Coupling Strength

YANG Zhuo-xuan1, MA Yuan-pei1 and YAN Guan2   

  1. 1 School of Economics and Management,North China Electric Power University,BeiJing 102206,China
    2 School of Management Science and Engineering,Central University of Finance and Economics,BeiJing 100081,China
  • Published:2020-07-07
  • About author:YANG Zhuo-xuan, born in 1998, postgraduate.Her maJor research interests include financial management and computer science and technology.
    YAN Guan, Ph.D.Her research interests include data mining and management science.
  • Supported by:
    This work was supported by the National Natural Science Foundation of China (71401233) and National Natural Science Foundation of BeiJing(9182015).

Abstract: In capital markets,groups can be divided according to how closely traders are connected,resulting in specific community structures.Community structure detection is one of the most interesting issues in the study of social networks.However,there are few polynomial time algorithms that can detect the community structure quickly and accurately.Inspired by the famous theory of modularity design optimization,in this paper,the idea of using a novel k-strength relationship to represent the coupling distance between two nodes is proposed.Community structure detection algorithm is presented using a generalized modularity measure based on the k-strength matrix.To obtain the optimal number of communities,a new parameter-free structure is adopted,which uses the difference of eigenvalues of specific transition matrix as the boundary of community classification.Finally,the algorithm is applied on both benchmark network and real network.Theoretical analysis and experiments show that the algorithm can detect communities quickly and accurately,and is easy to be extended to large scale real networks.

Key words: k-strength relationship, Community structure, Coupling distance, Optimal number of communities, Polynomial time, Social network

CLC Number: 

  • TP391
[1] NEWMAN M E J.Fast Algorithm for Detecting CommunityStructure in Networks.Physical Review E,2004,69:066133.
[2] NEWMAN M E J,GIRVAN M.Finding and Evaluating Community Structure in Networks.Physical Review E,2004,69:026113.
[3] NEWMAN M E J.Modularity and Community Structure in Networks.Proc Natl Acad Sci,2006,103:8577-8582.
[4] GAREY M R,JOHNSON D S.Computers and Intractability:A Guide to the Theory of NP-Completeness.San Francisco:Freeman,1979.
[5] SCOTT J.Social Network Analysis:A Handbook.London:Sage Publications,2000.
[6] GIRVAN M,NEWMAN M E J.Community Structure in Social and Biological Networks.Proc Natl Acad Sci,2002,99:7821-7826.
[7] ZHANG X S,WANG R S,WANG Y,et al.Modularity Optimization in Community Detection of Complex Networks.Europhysics Letters,2009,87:38002.
[8] ZHANG X S,LI Z,WANG R S,et al.A Combinatorial Model and Algorithm for Globally Searching Community Structure in Complex Networks.J.Comb.Optim.,2012,23(4):425-442.
[9] RADICCHI F,CASTELLANO C,CECCONI F,et al.Defining and Identifying Communities in Networks.Proc Natl Acad Sci,2004,101(9):2658-2663.
[10] LATAPY M,PONS P.Proceedings of the 20th International Symposium on Computer and Information Sciences.Lecture Notes in Computer Science,2005,3733:284-293.
[11] KERNIGHAN B W,LIN S,BELL.An Efficient Heuristic Procedure for Partitioning Graphs.System Technical Journal,1970,49:291-307.
[12] LI H J,ZHANG X S.Analysis of Stability of Community Structure Across Multiple Hierarchical Levels.Europhysics Letters,2013,103:58002.
[13] LI H J,WANG Y,WU L Y,et al.Potts Model Based on a Markov Process Computation Solves the Community Structure Problem Effectively.Physical Review E,2012,86:016109.
[14] BRANDES U.An Algorithm to Detect Community by Geodesic Line in Social Networks.International Journal on Advances in Information Sciences and Service Sciences,2006,3:0608255.
[15] HUANG L C,YEN T J,CHOU S C T.International Conference on Advances in Social Networks Analysis and Mining//IEEE Computer Society.2011:110-117.
[16] MUCHA P J.Community Structure in Time-Dependent,Multiscale,and Multiplex Networkset.Science,2010(328):876-878.
[17] GUTTMANN-BECK N,HASSIN.Approximation Algorithms for Minimum K-Cut.Algorithmica,2000(27):198-207.
[18] GAREY M R,JONSON D S.Computers and Intractability:A Guide to the Theory of NP-Completeness.San Francisco:Freeman,1979.
[19] MAKI D P.Mathematical Models and Applications,with Emphasis on social,life,and Management sciences.San Francisco:Prentice Hall College Div,1973.
[20] XIA Z Y,BU Z.Community Detection Based on a Semantic Network.Knowledge-Based Systems,2012(26):30-39.
[21] W N E,LI T,VANDEN-EIJNDEN E.Optimal Partition and Effective Dynamics of Complex Networks.Proc Natl Acad Sci,2008,105(23):7907-7912.
[22] DANON L,DUCH J,GUILERA D.Comparing Community Structure Identification.J.Stat.Mech,2005,29:P09008.
[23] BLONDEL V D,GUILLAUME J L,LAMBIOTTE R,et al.Fast Unfolding of Communities in Large Networks.J.Stat.Mech,2005,10:P10008.
[24] ROSVALL M,BERGSTROM C T.Maps of Random Walks on Complex Networks Reveal Community Structure.Proc Natl Acad Sci,2008,105(4):1118-1123.
[25] PALLA G,DERENYI I,FARKAS I.Uncovering the Overlapping Community Structure of Complex Networks in Nature and Society.Nature,2005,435:814-818.
[26] LI Z P,ZHANG S H,WANG R S,et al.Quantitative Function for Community Detection.Physical Review E,2008,77:036109.
[27] LANCICHINETTI A,FORTUNATO S.Community Detection Algorithms:A Comparative Analysis.Physical Review E,2009,80:056117.
[1] ZHENG Wen-ping, LIU Mei-lin, YANG Gui. Community Detection Algorithm Based on Node Stability and Neighbor Similarity [J]. Computer Science, 2022, 49(9): 83-91.
[2] WANG Jian, PENG Yu-qi, ZHAO Yu-fei, YANG Jian. Survey of Social Network Public Opinion Information Extraction Based on Deep Learning [J]. Computer Science, 2022, 49(8): 279-293.
[3] WEI Peng, MA Yu-liang, YUAN Ye, WU An-biao. Study on Temporal Influence Maximization Driven by User Behavior [J]. Computer Science, 2022, 49(6): 119-126.
[4] YU Ai-xin, FENG Xiu-fang, SUN Jing-yu. Social Trust Recommendation Algorithm Combining Item Similarity [J]. Computer Science, 2022, 49(5): 144-151.
[5] CHANG Ya-wen, YANG Bo, GAO Yue-lin, HUANG Jing-yun. Modeling and Analysis of WeChat Official Account Information Dissemination Based on SEIR [J]. Computer Science, 2022, 49(4): 56-66.
[6] ZUO Yuan-lin, GONG Yue-jiao, CHEN Wei-neng. Budget-aware Influence Maximization in Social Networks [J]. Computer Science, 2022, 49(4): 100-109.
[7] GUO Lei, MA Ting-huai. Friend Closeness Based User Matching [J]. Computer Science, 2022, 49(3): 113-120.
[8] SHAO Yu, CHEN Ling, LIU Wei. Maximum Likelihood-based Method for Locating Source of Negative Influence Spreading Under Independent Cascade Model [J]. Computer Science, 2022, 49(2): 204-215.
[9] WANG Jian, WANG Yu-cui, HUANG Meng-jie. False Information in Social Networks:Definition,Detection and Control [J]. Computer Science, 2021, 48(8): 263-277.
[10] TAN Qi, ZHANG Feng-li, WANG Ting, WANG Rui-jin, ZHOU Shi-jie. Social Network User Influence Evaluation Algorithm Integrating Structure Centrality [J]. Computer Science, 2021, 48(7): 124-129.
[11] ZHANG Ren-zhi, ZHU Yan. Malicious User Detection Method for Social Network Based on Active Learning [J]. Computer Science, 2021, 48(6): 332-337.
[12] BAO Zhi-qiang, CHEN Wei-dong. Rumor Source Detection in Social Networks via Maximum-a-Posteriori Estimation [J]. Computer Science, 2021, 48(4): 243-248.
[13] ZHANG Shao-jie, LU Xu-dong, GUO Wei, WANG Shi-peng, HE Wei. Prevention of Dishonest Behavior in Supply-Demand Matching [J]. Computer Science, 2021, 48(4): 303-308.
[14] HE Bin, XU Dao-yun. Community Structure of Regular (3,4)-CNF Formula [J]. Computer Science, 2021, 48(4): 26-30.
[15] GAO Ji-ji, YUE Xue-rong, CHEN Zhi-bin. Approximate Ratios Analysis of New Algorithm for Classical Parallel Scheduling [J]. Computer Science, 2021, 48(4): 37-42.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!