Journal Home > Volume 26 , Issue 5

Graph clustering, i.e., partitioning nodes or data points into non-overlapping clusters, can be beneficial in a large varieties of computer vision and machine learning applications. However, main graph clustering schemes, such as spectral clustering, cannot be applied to a large network due to prohibitive computational complexity required. While there exist methods applicable to large networks, these methods do not offer convincing comparisons against known ground truth. For the first time, this work conducts clustering algorithm performance evaluations on large networks (consisting of one million nodes) with ground truth information. Ideas and concepts from game theory are applied towards graph clustering to formulate a new proposed algorithm, Game Theoretical Approach for Clustering (GTAC). This theoretical framework is shown to be a generalization of both the Label Propagation and Louvain methods, offering an additional means of derivation and analysis. GTAC introduces a tuning parameter which allows variable algorithm performance in accordance with application needs. Experimentation shows that these GTAC algorithms offer scalability and tunability towards big data applications.


menu
Abstract
Full text
Outline
About this article

Game Theoretical Approach for Non-Overlapping Community Detection

Show Author's information Baohua SunRichard Al-BayatyQiuyuan HuangDapeng Wu( )
Department of Electrical and Computer Engineering, University of Florida, Gainesville, FL 32611, USA

Abstract

Graph clustering, i.e., partitioning nodes or data points into non-overlapping clusters, can be beneficial in a large varieties of computer vision and machine learning applications. However, main graph clustering schemes, such as spectral clustering, cannot be applied to a large network due to prohibitive computational complexity required. While there exist methods applicable to large networks, these methods do not offer convincing comparisons against known ground truth. For the first time, this work conducts clustering algorithm performance evaluations on large networks (consisting of one million nodes) with ground truth information. Ideas and concepts from game theory are applied towards graph clustering to formulate a new proposed algorithm, Game Theoretical Approach for Clustering (GTAC). This theoretical framework is shown to be a generalization of both the Label Propagation and Louvain methods, offering an additional means of derivation and analysis. GTAC introduces a tuning parameter which allows variable algorithm performance in accordance with application needs. Experimentation shows that these GTAC algorithms offer scalability and tunability towards big data applications.

Keywords: clustering, label propagation, community detection, game theory, big data analytics

References(42)

[1]
S. Fortunato, Community detection in graphs, Phys. Rep., vol. 486, nos. 3–5, pp. 75–174, 2010.
[2]
U. Von Luxburg, A tutorial on spectral clustering, Statist. Comput., vol. 17, no. 4, pp. 395–416, 2007.
[3]
J. B. Shi and J. Malik, Normalized cuts and image segmentation, IEEE Trans. Pattern Anal. Mach. Intell., vol. 22, no. 8, pp. 888–905, 2000.
[4]
M. E. J. Newman, Modularity and community structure in networks, Proc. Natl. Acad. Sci. USA, vol. 103, no. 23, pp. 8577–8582, 2006.
[5]
S. Fortunato and M. Barthélemy, Resolution limit in community detection, Proc. Natl. Acad. Sci. USA, vol. 104, no. 1, pp. 36–41, 2007.
[6]
A. Lancichinetti and S. Fortunato, Limits of modularity maximization in community detection, Phys. Rev.E, vol. 84, no. 6, p. 066122, 2011.
[7]
M. Rosvall and C. T. Bergstrom, Multilevel compression of random walks on networks reveals hierarchical organization in large integrated systems, PLoS One, vol. 6, no. 4, p. e18209, 2011.
[8]
M. Rosvall and C. T. Bergstrom, Maps of random walks on complex networks reveal community structure, Proc. Natl. Acad. Sci. USA, vol. 105, no. 4, pp. 1118–1123, 2008.
[9]
U. N. Raghavan, R. Albert, and S. Kumara, Near linear time algorithm to detect community structures in large-scale networks, Phys. Rev.E, vol. 76, no. 3, p. 036106, 2007.
[10]
V. D. Blondel, J. L. Guillaume, R. Lambiotte, and E. Lefebvre, Fast unfolding of communities in large networks, J. Statist. Mech.: Theory Exp., vol. 2008, no. 10, p. P10008, 2008.
[11]
A. Browet, P. Absil, and P. Van Dooren, Fast community detection using local neighbourhood search, arXiv preprint arXiv: 1308.6276, 2013.
[12]
Z. Bu, H. J. Li, C. C. Zhang, J. Cao, A. H. Li, and Y. Shi, Graph K-means based on leader identification, dynamic game, and opinion dynamics, IEEE Trans. Knowledge Data Eng., vol. 32, no. 7, pp. 1348–1361, 2019.
[13]
J. Cao, Z. Bu, Y. Y. Wang, H. Yang, J. C. Jiang, and H. J. Li, Detecting prosumer-community groups in smart grids from the multiagent perspective, IEEE Trans. Syst., Man, Cybernet.: Syst., vol. 49, no. 8, pp. 1652–1664, 2019.
[14]
H. J. Li, Z. Bu, Z. Wang, and J. Cao, Dynamical clustering in electronic commerce systems via optimization and leadership expansion, IEEE Trans. Ind. Informatics, vol. 16, no. 8, pp. 5327–5334, 2019.
[15]
H. J. Li, Z. Bu, Z. Wang, J. Cao, and Y. Shi, Enhance the performance of network computation by a tunable weighting strategy, IEEE Trans. Emerg. Topics Comput. Intell., vol. 2, no. 3, pp. 214–223, 2018.
[16]
H. J. Li, Q. Wang, S. F. Liu, and J. Hu, Exploring the trust management mechanism in self-organizing complex network based on game theory, Phys.A: Statist. Mech. Appl., vol. 524, p. 123514, 2020.
[17]
P. J. McSweeney, K. Mehrotra, and J. C. Oh, A game theoretic framework for community detection, in Proc. 2012 IEEE/ACM Int. Conf. on Advances in Social Networks Analysis and Mining (ASONAM), Istanbul, Turkey, 2012, pp. 227–234.
[18]
R. Narayanam and Y. Narahari, A game theory inspired, decentralized, local information based algorithm for community detection in social graphs, in Proc. 21st Int. Conf. on Pattern Recognition (ICPR), Tsukuba, Japan, 2012, pp. 1072–1075.
[19]
R. I. Lung, A. Gog, and C. Chira, A game theoretic approach to community detection in social networks, in Nature Inspired Cooperative Strategies for Optimization (NICSO 2011), D. A. Pelta, N. Krasnogor, D. Dumitrescu, C. Chira, and R. Lung, eds. Berlin, Germany: Springer, 2011, pp. 121–131.
[20]
W. Chen, Z. M. Liu, X. R. Sun, and Y. J. Wang, A game-theoretic framework to identify overlapping communities in social networks, Data Min. Knowl. Disc., vol. 21, no. 2, pp. 224–240, 2010.
[21]
W. Chen, Z. M. Liu, X. R. Sun, and Y. J. Wang, Community detection in social networks through community formation games, in Proc. Twenty-Second Int. Joint Conf. on Artificial Intelligence-Volume Volume Three, Barcelona, Spain, 2011, pp. 2576–2581.
[22]
Y. Narahari and R. Narayanam, Game theoretic models for social network analysis, in Proc. 20th Int. Conf. on World Wide Web, Hyderabad, India, 2011, pp. 291–292.
[23]
M. J. Osborne, An Introduction to Game Theory. New York, NY, USA: Oxford University Press, 2004.
[24]
J. Von Neumann and O. Morgenstern, Theory of Games and Economic Behavior (Commemorative Edition). Princeton, NJ, USA: Princeton University Press, 2007.
[25]
J. Nash, Equilibrium points in n-person games, Proc. Natl. Acad. Sci. USA, vol. 36, no. 1, pp. 48–49, 1950.
[26]
J. Nash, Non-cooperative games, Ann. Math., vol. 54, no. 2, pp. 286–295, 1951.
[27]
R. D. McKelvey and A. McLennan, Computation of equilibria in finite games, Handb. Comput. Econ., vol. 1, pp. 87–142, 1996.
[28]
M. E. J. Newman, Analysis of weighted networks, Phys. Rev.E, vol. 70, no. 5, p. 056131, 2004.
[29]
K. Altisen, S. Devismes, A. Gerbaud, and P. Lafourcade, Analysis of random walks using tabu lists, in Proc. 19th Int. Colloquium on Structural Information and Communication Complexity, Reykjavik, Iceland, 2012, pp. 254–266.
[30]
G. Karypis, E. H. Han, and V. Kumar, Chameleon: Hierarchical clustering using dynamic modeling, Computer, vol. 32, no. 8, pp. 68–75, 1999.
[31]
A. Lancichinetti, S. Fortunato, and F. Radicchi, Benchmark graphs for testing community detection algorithms, Phys. Rev.E, vol. 78, no. 4, p. 046110, 2008.
[32]
A. Lancichinetti and S. Fortunato, Community detection algorithms: A comparative analysis, Phys. Rev.E, vol. 80, no. 5, p. 056117, 2009.
[33]
A. Lancichinetti, F. Radicchi, J. J. Ramasco, and S. Fortunato, Finding statistically significant communities in networks, PLoS One, vol. 6, no. 4, p. e18961, 2011.
[34]
S. Gregory, Finding overlapping communities in networks by label propagation, New J. Phys., vol. 12, no. 10, p. 103018, 2010.
[35]
B. H. Sun and D. P. Wu, Self-organizing-queue based clustering, IEEE Signal Process. Lett., vol. 19, no. 12, pp. 902–905, 2012.
[36]
H. Kwak, C. Lee, H. Park, and S. Moon, What is twitter, a social network or a news media? in Proc. 19th Int. Conf. on World Wide Web, Raleigh, NC, USA, 2010, pp. 591–600.
[37]
L. Danon, A. J. Duch, and A. Arenas, Comparing community structure identification, J. Statist. Mech.: Theory Exp., vol. 2005, no. 9, pp. 1–10, 2005.
[38]
J. J. Whang, X. Sui, and I. S. Dhillon, Scalable and memory-efficient clustering of large-scale social networks, in Proc. IEEE 12th Int. Conf. on Data Mining (ICDM), Brussels, Belgium, 2012, pp. 705–714.
[39]
W. W. Zachary, An information flow model for conflict and fission in small groups, J. Anthropol. Res., vol. 33, no. 4, pp. 452–473, 1977.
[40]
A. Lancichinetti, LFR benchmark code, https://sites.google.com/site/andrealancichinetti/files, 2010.
[41]
Amazon EC2 instance types, http://aws.amazon.com/en/ec2/instance-types/, 2013.
[42]
V. D. Blondel, J. Guillaume, R. Lambiotte, and E. Lefebvre, Louvain method: Finding communities in large networks, https://sites.google.com/site/findcommunities/, 2008.
Publication history
Copyright
Acknowledgements
Rights and permissions

Publication history

Received: 10 December 2019
Revised: 24 May 2020
Accepted: 25 May 2020
Published: 20 April 2021
Issue date: October 2021

Copyright

© The author(s) 2021

Acknowledgements

The authors would like to thank Dong Wang for his aid in conducting the experiments on the cloud computing platform.

Rights and permissions

© The author(s) 2021. The articles published in this open access journal are distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/).

Return