|
|
|
| Network Structure-Enhanced Extremal Optimization Based Semi-supervised Algorithm for Community Detection |
| DU Mei, HU Xue-Gang, LI Lei, HE Wei |
| School of Computer and Information, Hefei University of Technology, Hefei 230009 |
|
|
|
|
Abstract Community structure detection is extensively studied. However, the performance of the existing community detection methods becomes lower as the noise in the related networks increases. To solve this problem, the prior knowledge in the form of pairwise constraints and existing community detection methods are combined to guide the process of community detection, and an extremal optimization based semi-supervised algorithm is proposed for community detection. The experimental results on networks show that compared with the existing methods, the proposed method improves the accuracy of community detection and shows good performance with the noise in the network.
|
|
Received: 26 June 2013
|
|
|
|
|
|
[1] Kernighan B W, Lin S. An Efficient Heuristic Procedure for Par-titioning Graphs. Bell System Technical Journal, 1970, 49(2): 291-307
[2] Fortunato S. Community Detection in Graphs. Physics Reports, 2010, 486: 75-174
[3] Allahverdyan A E, Ver Steeg G, Galstyan A. Community Detection with and without Prior Information [EB/OL].[2013-04-01]. http://iopscience.iop.org/0295-5075/90/1/18002/pdf/0295-5075_90_1_18002.pdf
[4] Ma X K, Gao L, Yong X R, et al. Semi-supervised Clustering Algorithm for Community Structure Detection in Complex Networks. Physica A: Statistical Mechanics and Its Applications, 2010, 389(1): 187-197
[5] Ver Steeg G, Galstyan A, Allahverdyan A E. Statistical Mechanics of Semi-supervised Clustering in Sparse Graphs [EB/OL].[2013-01-01].http://iopscience.iop.org/1742-5468/2011/08/P08009/pdf/jstatll_08_p08009.pdf
[6] Zhang Z Y. Community Structure Detection in Complex Networks with Partial Background Information [EB/OL].[2013-04-01]. http://iopscience.iop.org/0295-5075/101/4/48005/pdf/0295-5075_101_4_48005.pdf
[7] Eaton E, Mansbach R. A Spin-Glass Model for Semi-supervised Community Detection // Proc of the 26th AAAI Conference on Artificial Intelligence. Toronto, Canada, 2012: 900-906
[8] Leng M W, Yao Y K, Cheng J J, et al. Active Semi-supervised Community Detection Algorithm with Label Propagation // Proc of the 18th International Conference on Database Systems for Advanced Applications. Wuhan, China, 2013, Ⅱ: 324-338
[9] Silva T C, Zhao L. Semi-supervised Learning Guided by the Modularity Measure in Complex Networks. Neurocomputing, 2012, 78(1): 30-37
[10] Newman M E J, Girvan M. Finding and Evaluating Community Structure in Networks [EB/OL].[2013-04-01]. http://journals.aps.org/pre/pdf/10.1103/PhysRevE.69.026113
[11] Radicchi F, Castellano C, Cecconi F, et al. Defining and Identi-fying Communities in Networks. Proceedings of the National Academy of Sciences of the United States of America, 2004, 101(9): 2658-2663
[12] Tsuchiura H, Ogata M, Tanaka Y, et al. Electronic States around a Vortex Core in High-Tc Superconductors Based on the t-J Model [EB/OL].[2013-04-01]. http://journals.aps.org/prb/pdf/10.1103/PhysRevB.68.012509
[13] Newman M E J. Fast Algorithm for Detecting Community Structure in Networks [EB/OL].[2013-04-01]. http://journals.aps.org/pre/pdf/10.1103/PhysRevE.69.066133
[14] Guimera R, Amaral L A N. Functional Cartography of Complex Metabolic Networks. Nature, 2005, 433: 895-900
[15] Duch J, Arenas A. Community Detection in Complex Networks Using Extremal Optimization [EB/OL].[2013-04-01]. http://journals.aps.org/pre/pdf/10.1103/PhysRevE.72.027104
[16] Newman M E J. Finding Community Structure in Networks Using the Eigenvectors of Matrices [EB/OL].[2013-04-01]. http://journals.aps.org/pre/pdf/10.1103/PhysRevE.74.036104
[17] Newman M E J. Analysis of Weighted Networks [EB/OL].[2013-04-01]. http://journals.aps.org/pre/pdf/10.1103/PhysRevE.70.056131
[18] Fiedler M. Algebraic Connectivity of Graphs. Czechoslovak Mathematical Journal, 1973, 23(2): 298-305
[19] Pothen A, Simon H D, Liou K P. Partitioning Sparse Matrices with Eigenvectors of Graphs. SIAM Journal on Matrix Analysis and Applications, 1990, 11(3): 430-452
[20] Reichardt J, Bornholdt S. Detecting Fuzzy Community Structures in Complex Networks with a Potts Model[EB/OL]. [2013-05-28]. http://www.itp.uni-bremen.de/complex/pdf/prl218701.pdf
[21] Pons P, Latapy M. Computing Communities in Large Networks Using Random Walk // Proc of the 20th International Symposium on Computer and Information Sciences. Turkey, Istanbul, 2005: 284-293
[22] Wu F, Huberman B A. Finding Communities in Linear Time: A Physics Approach. The European Physical Journal B: Condensed
Matter and Complex Systems, 2004, 38(2): 331-338
[23] Boettcher S, Percus A G. Extremal Optimization: Methods Derived from Co-evolution // Proc of the Genetic and Evolutionary Computation Conference. Seattle, USA, 1999, Ⅰ: 825-832
[24] Wagstaff K, Cardie C. Clustering with Instance-Level Constraints // Proc of the 17th International Conference on Machine Learning. Palo Alto, USA, 2000: 1103-1110
[25] Zachary W W. An Information Flow Model for Conflict and Fission in Small Groups. Journal of Anthropological Research, 1977, 33(4): 452-473
[26] Lusseau D, Schneider K, Boisseau O J, et al. The Bottlenose Do-lphin Community of Doubtful Sound Features a Large Proportion of Long-Lasting Associations. Behavioral Ecology and Sociobiology, 2003, 54(4): 396-405
[27] Danon L, Diaz-Guilera A, Duch J, et al. Comparing Community Structure Identification [EB/OL].[2013-04-01]. http://iopscience.iop.org/1742-5468/2005/09/P09008/pdf/1742-5468_2005_09_P09008.pdf
[28] Lancichinetti A, Fortunato S, Radicchi F. Benchmark Graphs for Testing Community Detection Algorithms [EB/OL].[2013-04-01]. http://journals.aps.org/pre/pdf/10.1103/PhysRevE.78.046110 |
|
|
|
2015, Vol. 28 
