Fast Algorithm on Stochastic Block Model for Exploring General Communities
Author:
Affiliation:

  • Article
  • | |
  • Metrics
  • |
  • Reference [29]
  • |
  • Related
  • |
  • Cited by
  • | |
  • Comments
    Abstract:

    A stochastic block model can produce a wide variety of networks with different structures (named as general community, including traditional community, bipartite structure, hierarchical structure and etc); it also can detect general community in networks according to the rules of stochastic equivalence. However, the simple stochastic block model has some problems in modeling the generation of the networks and learning the models, showing poor results in fitting the practical networks. The GSB (general stochastic block) model is an extension of the stochastic block model, which is based on the idea of link community and is provided to detect general communities. But its complexity limits its applications in medium and large networks. In order to explore the latent structures of networks with different scales without prior knowledge about networks, a fast algorithm on the GSB model (FGSB) is designed to explore general communities in networks faster. FGSB dynamically learns the parameters related to the network structure in the process of iterations. It reduces the storage memory by reorganizing parameters to cut down unnecessary parameters, and saves the running time by pruning the related parameters of converging nodes and edges to decrease the computing time of each iteration. FGSB has the same ability of structure detection as the GSB model, but its complexities of time and storage are lower. Tests on synthetic benchmarks and real-world networks have demonstrated that FGSB not only can run faster than the algorithm of the GSB model in the similar accuracy, but also can detect general communities for large networks.

    Reference
    [1] Fortunato S. Community detection in graphs. Physics Reports, 2010,486(3):75-174.[doi: 10.1016/j.physrep.2009.11.002]
    [2] Karrer B, Newman MEJ. Stochastic blockmodels and community structure in networks. Physical Review E, 2011,83(11):016107.[doi: 10.1103/PhysRevE.83.016107]
    [3] Cheng XQ, Shen HW. Community structure of complex networks. Complex Systems and Complex Science, 2011,8(1):57-70 (in Chinese with English abstract).
    [4] Newman MEJ, Leicht EA. Mixture models and exploratory analysis in networks. Proc. of the National Academy of Sciences, 2007, 104(23):9564-9569.[doi: 10.1073/pnas.0610537104]
    [5] Shen HW, Cheng XQ, Guo J. Exploring the structural regularities in networks. Physical Review E, 2011,84(5):056111.[doi: 10. 1103/PhysRevE.84.056111]
    [6] Yang B, Liu J, Liu DY. Characterizing and extracting multiplex patterns in complex networks. IEEE Trans. on Systems, Man, and Cybernetics, 2012,42(2):469-481.[doi: 10.1109/TSMCB.2011.2167751]
    [7] Chai BF, Yu J, Jia CY, Yang TB, Jiang YW. Combining a popularity-productivity stochastic block model with a discriminativecontent model for general structure detection. Physical Review E, 2013,88(3):012807.
    [8] Fienberg SE, Wasserman S. Categorical data analysis of single sociometric relations. Sociological Methodology, 1981,12:156-192.[doi: 10.2307/270741]
    [9] Holland PW, Laskey KB, Leinhardt S. Stochastic blockmodels: First steps. Social Networks, 1983,5(2):109-137.[doi: 10.1016/0378-8733(83)90021-7]
    [10] Snijders T, Nowicki K. Estimation and prediction for stochastic blockmodels for graphs with latent block structure. Journal of Classification, 1997,14(1):75-100.[doi: 10.1007/s003579900004]
    [11] Nowicki K, Snijders T. Estimation and prediction for stochastic block structures. Journal of American Statistical Association, 2001, 96(455):1077-1087.[doi: 10.1198/016214501753208735]
    [12] Daudin J, Picard F, Robin S. A mixture model for random graphs. Statistical Computing, 2008,18(2):173-183.[doi: 10.1007/s11222-007-9046-7]
    [13] Latouche P, Birmele E, Ambroise C. Variational Bayesian inference and complexity control for stochastic block models. Statistical Modeling, 2012,12(1):93-115.[doi: 10.1177/1471082X1001200105]
    [14] Latouche P, Birmele E, Ambroise C. Overlapping stochastic block models with application to the French political blogosphere. The Annals of Applied Statistics, 2011,5(1):309-336.[doi: 10.1214/10-AOAS382]
    [15] Zanghi H, Ambroise C, Miele V. Fast online graph clustering via Erdös-Rényi mixture. Pattern Recognition, 2008,41(12): 3592-3599.[doi: 10.1016/j.patcog.2008.06.019]
    [16] McDaid AF, Murphy B, Friel N, Hurley NJ. Improved Bayesian inference for the stochastic block model with application to large networks. Computational Statistics and Data Analysis, 2013,60:12-31.[doi: 10.1016/j.csda.2012.10.021]
    [17] Airodi EM, Blei DM, Fienberg SE, Stephen E, Eric XE. Mixed membership stochastic blockmodels. Journal of Machine Learning Research, 2008,9(1):1981-2014.
    [18] Lorrain F, White HC. Structural equivalence of individuals in social networks. Journal of the American Statistical Association, 1971,1(1):49-80.
    [19] Everett MG, Borgatti SP. The centrality of groups and classes. Journal of Mathematical Sociology, 1999,23(3):181-201.[doi: 10. 1080/0022250X.1999.9990219]
    [20] Wasserman S, Anderson C. Stochastic a posteriori blockmodels: Construction and assessment. Social Networks, 1987,9:1-36.[doi: 10.1016/0378-8733(87)90015-3]
    [21] Cohn D, Chang H. Learning to probabilistically identify authoritative documents. In: Pat L, ed. Proc. of the 17th Int''l Conf. on Machine Learning. Morgan Kaufmann Publishers, 2000. 167-174.
    [22] Yang TB, Jin R, Chi Y, Zhu SH. Combining link and content for community detection: A discriminative approach. In: Proc. of the 15th ACM SIGKDD Int''l Conf. on Knowledge Discovery and Data Mining. New York: ACM, 2009. 927-936.
    [23] Yang TB, Chi Y, Zhu SH, Gong YH, Jin R. Directed network community detection: A popularity and productivity link model. In: Bing L, Srinivasan P, Chandrika K, eds. Proc. of the SIAM Conf. on Data Mining. SIAM, 2010. 742-753.
    [24] Ren W, Yan GY, Liao XP, Xiao L. Simple probabilistic algorithm for detecting community structure. Physical Review E, 2009, 79(3):036111.[doi: 10.1103/PhysRevE.79.036111]
    [25] Sinkkonen J, Aukia J, Kaski S. Inferring vertex properties from topology in large networks. In: Paolo F, Kristian K, Koji T, eds. Working Notes of the 5th Int''l Workshop on Mining and Learning with Graphs. 2007.
    [26] Gyenge A, Sinkkonen J, Benczur A. An efficient block model for clustering sparse graphs. In: Ulf B, Lise G, Sofus AM, eds. Proc. of the 8th Workshop on Mining and Learning with Graphs. New York: ACM, 2010. 62-69.[doi: 10.1145/1830252.1830261]
    [27] Ball B, Karrer B, Newman MEJ. An efficient and principled method for detecting communities in networks. Physical Review E, 2011,84(3):036103.[doi: 10.1103/PhysRevE.84.036103]
    [28] Hintze A, Adami C. Modularity and anti modularity in networks with arbitrary degree distribution. Biology Direct, 2010,5(32): 1-25.[doi: 10.1186/1745-6150-5-32]
    [29] Lancichinetti A, Fortunato S, Radicchi F. Benchmark graphs for testing community detection algorithms. Physical Review E, 2008,78(4):046110.[doi: 10.1103/PhysRevE.78.046110]
    Related
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

柴变芳,于剑,贾彩燕,王静红.一种基于随机块模型的快速广义社区发现算法.软件学报,2013,24(11):2699-2709

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:April 22,2013
  • Revised:July 17,2013
  • Online: November 01,2013
You are the first2041642Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063