» Download Article
A Model of Opinion Dynamics for Community Detection in Graphs
Estimation and Control of Networked Systems, Volume # | Part#
Authors
Morarescu, Irinel Constantin; Girard, Antoine
Digital Object Identifier (DOI)
10.3182/20100913-2-FR-4014.00001
Page Numbers:
251-256
Index Terms
Consensus problems; Randomized algorithms, gossip algorithms; Decentralized and cooperative optimization
Abstract
In this paper, we propose a new approach to the problem of community detection in graphs. It is based on a model of opinion dynamics with decaying confidence. This model is a multi-agent system where each agent receives the opinions of its neighbors and then updates its opinion by taking a weighted average of its own opinion and those of its neighbors that are within some confidence range. The confidence ranges are getting smaller at each time step: an agent gives repetitively confidence only to the neighbors that approach sufficiently fast its own opinion. Under that constraint, global consensus may not be achieved and the agents may only reach local agreement organizing themselves in communities. A characterization of these communities is given in terms of eigenvalues of normalized Laplacian matrices of graphs. This shows that our model of opinion dynamics with decaying confidence provides an appealing approach to community detection in graphs. Experimental results show that our approach is also effective.
References
L. Adamic and N. Glance, The political blogosphere and the 2004 U.S. election: divided they blog, Conf. on Knowledge Discovery in Data: Proc. of the 3rd int. workshop on Link discovery, 2005. V.D. Blondel and J.-L. Guillaume and R. Lambiotte and E. Lefebvre: Fast unfolding of communites in large networks, Journal of Statistical Mechanics: Theory and Experiment, vol. 1742-5468(08), pp. 10008+12, 2008. V. D. Blondel, J. M. Hendrickx, , and J.N. Tsitsiklis: On Krause's consensus formation model with state- dependent connectivity. IEEE Trans. on Automatic Control, vol. 54(11), pp. 2506-2517, 2009. U. Brandes, D. Delling, M. Gaertler, R. Gorke, M. Hoefer, Z. Nikoloski, and D. Wagner. On modularity clustering. IEEE Trans. on Knowledge and Data Engineering, vol. 20(2), pp. 172-188, 2008. F. Chung: Spectral Graph Theory, AMS, 1997. S. Fortunato: Community detection in graphs. Physics Reports, vol. 486, pp. 75-174, 2010. U. Krause: Soziale dynamiken mit vielen interakteuren. Eine problemskizze. In Modellierung und Simulation von Dynamiken mit vielen interagierenden Akteuren, pp. 37-51, 1997. R. Hegselmann and U. Krause: Opinion dynamics and bounded confidence models, analysis, and simulation. Journal of Artificial Societies and Social Simulation, vol. 5(3), 2002. I.-C. Morarescu and A. Girard: Opinion dynamics with de- caying confidence: application to community detection in graphs. ArXiv, 0911.5239, 2009. M.E.J. Newman and M. Girvan, Finding and evaluating community structure in networks, Physical Review E, vol. 69(2):026113, pp. 1-15, 2004. M.E.J. Newman, Modularity and community structure in networks, Proc. Natl. Acad. Sci. USA, vol. 103, pp. 8577-8582, 2006. W.W. Zachary: An information ow model for conflict and fission in small groups. Journal of anthropological research, vol. 33(4), pp. 452-473, 1977.