More Web Proxy on the site http://driver.im/

research-article

Stochastic Blockmodeling and Variational Bayes Learning for Signed Network Analysis

Authors:

Xuehua ZhaoAuthors Info & Claims

IEEE Transactions on Knowledge and Data Engineering, Volume 29, Issue 9

Pages 2026 - 2039

https://doi.org/10.1109/TKDE.2017.2700304

Published: 01 September 2017 Publication History

Abstract

Signed networks with positive and negative links attract considerable interest in their studying since they contain more information than unsigned networks. Community detection and sign (or attitude) prediction are still primary challenges, as the fundamental problems of signed network analysis. For this, a generative Bayesian approach is presented wherein 1) a signed stochastic blockmodel is proposed to characterize the community structure in the context of signed networks, by explicit formulating the distributions of the density and frustration of signed links from a stochastic perspective, and 2) a model learning algorithm is advanced by theoretical deriving a variational Bayes EM for the parameter estimation and variation-based approximate evidence for the model selection. The comparison of the above approach with the state-of-the-art methods on synthetic and real-world networks, shows its advantage in the community detection and sign prediction for the exploratory networks.

References

[1]

J. Tang, Y. Chang, C. Aggarwal, and H. Liu, “A survey of signed network mining in social media,” ACM Comput. Surveys (CSUR), vol. 49, no. 3, 2016, Art. no.

[2]

M. J. Mason, G. Fan, K. Plath, Q. Zhou, and S. Horvath, “Signed weighted gene co-expression network analysis of transcriptional regulation in murine embryonic stem cells,” BMC Genomics, vol. 10, no. 1, 2009, Art. no.

[3]

D. Cartwright and F. Harary, “Structural balance: A generalization of heider’s theory,” Psychological Rev., vol. 63, no. 5, pp. 277–293, 1956.

[4]

J. A. Davis, “Clustering and structural balance in graphs,” Human Relations, vol. 20, no. 2, pp. 181 –187, 1967.

[5]

M. Girvan and M. E. Newman, “Community structure in social and biological networks,” in Proc. Nat. Academy Sci., vol. 99, 2002, pp. 7821– 7826.

[6]

M. E. Newman, “Fast algorithm for detecting community structure in networks,” Phys. Rev. Eval., vol. 69, no. 6, 2004, Art. no.

[7]

H. Zhou, “Distance, dissimilarity index, and network community structure,” Phys. Rev. Eval., vol. 67, no. 6, 2003, Art. no. 1901.

[8]

G. Palla, I. Derényi, I. Farkas, and T. Vicsek, “Uncovering the overlapping community structure of complex networks in nature and society,” Nature, vol. 435, no. 7043, pp. 814–818, 2005.

[9]

M. Mitrović and B. Tadić, “Spectral and dynamical properties in classes of sparse networks with mesoscopic inhomogeneities,” Phys. Rev. Eval., vol. 80, no. 2, 2009, Art. no.

[10]

C. Pizzuti, “Ga-net: A genetic algorithm for community detection in social networks,” in Proc. 10th Int. Conf Parallel Problem Solving Nature, 2008, pp. 1081–1090.

[11]

V. A. Traag and J. Bruggeman, “Community detection in networks with positive and negative links,” Phys. Rev. Eval., vol. 80, no. 3, 2009, Art. no.

[12]

P. Esmailian and M. Jalili, “Community detection in signed networks: The role of negative ties in different scales,” Sci. Rep., vol. 5, 2015, Art. no.

[13]

P. Anchuri and M. Magdon-Ismail, “Communities and balance in signed networks: A spectral approach,” in Proc. IEEE/ACM Int. Conf. Adv. Social Netw. Anal. Mining, 2012, pp. 235–242.

[14]

B. Yang, W. Cheung, and J. Liu, “Community mining from signed social networks,” IEEE Trans. Knowl. Data Eng. , vol. 19, no. 10, pp. 1333–1348, Oct. 2007.

Digital Library

[15]

Z. Huang and Y. Qiu, “A multiple-perspective approach to constructing and aggregating citation semantic link network,” Future Gener. Comput. Syst., vol. 26, no. 3, pp. 400–407, 2010.

Digital Library

[16]

Q. Cai, M. Gong, B. Shen, L. Ma, and L. Jiao, “Discrete particle swarm optimization for identifying community structures in signed social networks,” Neural Netw., vol. 58, pp. 4– 13, 2014.

Digital Library

[17]

C. Liu, J. Liu, and Z. Jiang, “A multiobjective evolutionary algorithm based on similarity for community detection from signed social networks,” IEEE Trans. Cybern., vol. 44, no. 12, pp. 2274–2287, Dec. 2014.

[18]

M. Gong, Q. Cai, X. Chen, and L. Ma, “Complex network clustering by multiobjective discrete particle swarm optimization based on decomposition,” IEEE Trans. Evolutionary Comput., vol. 18, no. 1, pp. 82– 97, Feb. 2014.

[19]

P. Doreian and A. Mrvar, “A partitioning approach to structural balance,” Social Netw. , vol. 18, no. 2, pp. 149–168, 1996.

[20]

P. Doreian and A. Mrvar, “Partitioning signed social networks,” Social Netw., vol. 31, no. 1, pp. 1–11, 2009.

[21]

N. Larusso, P. Bogdanov, and A. Singh, “Identifying communities with coherent and opposing views,” in Proc. 15th Annu. Graduate Student Workshop Comput., 2010, pp. 31–32.

[22]

N. Bansal, A. Blum, and S. Chawla, “Correlation clustering,” Mach. Learn., vol. 56, no. 1 –3, pp. 89–113, 2004.

Digital Library

[23]

P. W. Holland and S. Leinhardt, “An exponential family of probability distributions for directed graphs,” J. Amer. Statist. Assoc., vol. 76, no. 373, pp. 33 –50, 1981.

[24]

E. M. Airoldi, D. M. Blei, S. E. Fienberg, and E. P. Xing, “Mixed membership stochastic blockmodels,” J. Mach. Learn. Res., vol. 9, pp. 1981 –2014, 2008.

Digital Library

[25]

P. Latouche, E. Birmelé, and C. Ambroise, “ Overlapping stochastic block models with application to the french political blogosphere,” Annal. Appl. Statist., vol. 5, no. 1, pp. 309 –336, 2011.

[26]

T. Yang, Y. Chi, S. Zhu, Y. Gong, and R. Jin, “Detecting communities and their evolutions in dynamic social network—a bayesian approach,” Mach. Learn., vol. 82, no. 2, pp. 157–189, 2011.

Digital Library

[27]

B. Yang, J. Liu, and D. Liu, “Characterizing and extracting multiplex patterns in complex networks,” IEEE Trans. Syst. Manage. Cybernet. Part B Cybernet., vol. 42, no. 2, pp. 469 –481, Apr. 2012.

Digital Library

[28]

B. Yang, X. Zhao, and X. Liu, “Bayesian approach to modeling and detecting communities in signed network,” in Proc. 29th AAAI Conf. Artif. Intell., 2015, pp. 1952–1958.

[29]

T. A. Snijders and K. Nowicki, “Estimation and prediction for stochastic blockmodels for graphs with latent block structure,” J. Classification, vol. 14, no. 1, pp. 75–100, 1997.

[30]

J.-J. Daudin, F. Picard, and S. Robin, “A mixture model for random graphs,” Statist. Comput., vol. 18, no. 2, pp. 173–183, 2008.

Digital Library

[31]

J. M. Hofman and C. H. Wiggins, “Bayesian approach to network modularity,” Phys. Rev. Lett. , vol. 100, no. 25, 2008, Art. no.

[32]

J. Q. Jiang, “Stochastic block model and exploratory analysis in signed networks,” Phys. Rev. Eval., vol. 91, no. 6, 2015, Art. no.

[33]

Y. Chen, X. Wang, B. Yuan, and B. Tang, “Overlapping community detection in networks with positive and negative links,” J. Statist. Mech. Theory Exp., vol. 2014, no. 3, 2014, Art. no.

[34]

L. I. Kuncheva and S. T. Hadjitodorov, “Using diversity in cluster ensembles,” in Proc. IEEE Int. Conf. Syst. Manage. Cybernet., vol. 2, 2004, pp. 1214–1219.

[35]

S. Kropivnik and A. Mrvar, “An analysis of the slovene parliamentary parties network,” Develop. Data Anal., A. Ferligoj, A. Kramberger, eds., pp. 209–216, 1996.

[36]

K. E. Read, “Cultures of the central highlands, new guinea,” Southwestern J. Anthropology, vol. 10, no. 1, pp. 1 –43, 1954.

[37]

S. F. Sampson, “Crisis in a cloister,” Ph.D. dissertation, Ithaca, NY 14850: Cornell University, 1969.

[38]

A. Lancichinetti, S. Fortunato, and F. Radicchi, “Benchmark graphs for testing community detection algorithms,” Phys. Rev. Eval., vol. 78, no. 4, 2008, Art. no.

[39]

C.-J. Hsieh, K.-Y. Chiang, and I. S. Dhillon, “Low rank modeling of signed networks,” in Proc. 18th ACM SIGKDD Int. Conf. Knowl. Discovery Data Mining, 2012, pp. 507–515.

[40]

K.-Y. Chiang, C.-J. Hsieh, N. Natarajan, I. S. Dhillon, and A. Tewari, “Prediction and clustering in signed networks: A local to global perspective,” J. Mach. Learn. Res., vol. 15, no. 1, pp. 1177–1213, 2014.

Digital Library

[41]

K.-Y. Chiang, N. Natarajan, A. Tewari, and I. S. Dhillon, “Exploiting longer cycles for link prediction in signed networks,” in Proc. 20th ACM Int. Conf. Inform. Knowl. Manage. , 2011, pp. 1157–1162.

[42]

J. Leskovec, D. Huttenlocher, and J. Kleinberg, “ Predicting positive and negative links in online social networks,” in Proc 19th Int. Conf. World Wide Web, 2010, pp. 641–650.

Digital Library

Cited By

Deng JHuang DZhang B(2024)Distributed Pseudo-Likelihood Method for Community Detection in Large-Scale NetworksACM Transactions on Knowledge Discovery from Data10.1145/365730018:7(1-25)Online publication date: 19-Jun-2024
https://dl.acm.org/doi/10.1145/3657300
Chakraborty RDas RChandra J(2023)SigGAN: Adversarial Model for Learning Signed Relationships in NetworksACM Transactions on Knowledge Discovery from Data10.1145/353261017:1(1-20)Online publication date: 20-Feb-2023
https://dl.acm.org/doi/10.1145/3532610
Wang LZhang XLi KZhang S(2022)Semi-supervised learning for k-dependence Bayesian classifiersApplied Intelligence10.1007/s10489-021-02531-y52:4(3604-3622)Online publication date: 1-Mar-2022
https://dl.acm.org/doi/10.1007/s10489-021-02531-y
Show More Cited By

Index Terms

Stochastic Blockmodeling and Variational Bayes Learning for Signed Network Analysis

Index terms have been assigned to the content through auto-classification.

Recommendations

Latent-Space Variational Bayes

Variational Bayesian Expectation-Maximization (VBEM), an approximate inference method for probabilistic models based on factorizing over latent variables and model parameters, has been a standard technique for practical Bayesian inference. In this paper,...
Averaged collapsed variational bayes inference

This paper presents the Averaged CVB (ACVB) inference and oers convergence-guaranteed and practically useful fast Collapsed Variational Bayes (CVB) inferences. CVB inferences yield more precise inferences of Bayesian probabilistic models than ...
Stochastic variational inference

We develop stochastic variational inference, a scalable algorithm for approximating posterior distributions. We develop this technique for a large class of probabilistic models and we demonstrate it with two probabilistic topic models, latent Dirichlet ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Knowledge and Data Engineering

IEEE Transactions on Knowledge and Data Engineering Volume 29, Issue 9

Sept. 2017

293 pages

ISSN:1041-4347

Issue’s Table of Contents

1041-4347 © 2016 IEEE.

Publisher

IEEE Educational Activities Department

United States

Publication History

Published: 01 September 2017

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Deng JHuang DZhang B(2024)Distributed Pseudo-Likelihood Method for Community Detection in Large-Scale NetworksACM Transactions on Knowledge Discovery from Data10.1145/365730018:7(1-25)Online publication date: 19-Jun-2024
https://dl.acm.org/doi/10.1145/3657300
Chakraborty RDas RChandra J(2023)SigGAN: Adversarial Model for Learning Signed Relationships in NetworksACM Transactions on Knowledge Discovery from Data10.1145/353261017:1(1-20)Online publication date: 20-Feb-2023
https://dl.acm.org/doi/10.1145/3532610
Wang LZhang XLi KZhang S(2022)Semi-supervised learning for k-dependence Bayesian classifiersApplied Intelligence10.1007/s10489-021-02531-y52:4(3604-3622)Online publication date: 1-Mar-2022
https://dl.acm.org/doi/10.1007/s10489-021-02531-y
de Santiago RLamb L(2020)Exact Signed Modularity Density Maximization Solutions and Their Real Meaning^*2020 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC48606.2020.9185736(1-7)Online publication date: 19-Jul-2020
https://dl.acm.org/doi/10.1109/CEC48606.2020.9185736

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents