Fuzzy Clustering in Assortative and Disassortative Networks
Ryoichi Kojima*,, Roberto Legaspi*, and Toshiaki Murofushi**
*KDDI Research, Inc.
2-1-15 Ohara, Fujimino-shi, Saitama 356-8502, Japan
**Department of Mathematical and Computing Science, School of Computing, Tokyo Institute of Technology
2-12-1-W8-49 Ookayama, Meguro-ku, Tokyo 152-8550, Japan
Despite the significance of assortativity as a property of networks that paves for the emergence of new structural types, surprisingly, there has been little research done on assortativity. Assortative networks are perhaps among the most prominent examples of complex networks believed to be governed by common phenomena, thereby producing structures far from random. Further, certain vertices possess high centrality and can be regarded as significant and influential vertices that can become cluster centers that connect with high membership to many of the surrounding vertices. We propose a fuzzy clustering method to meaningfully characterize assortative, as well as disassortative, networks by adapting the Bonacichi’s power centrality to seek the high degree centrality vertices to become cluster centers. Moreover, we leverage our novel modularity function to determine the optimal number of clusters, as well as the optimal membership among clusters. However, due to the difficulty of finding real-world assortative network datasets that come with ground truths, we evaluated our method using synthetic data but possibly bearing resemblance to real-world network datasets as they were generated by the Lancichinetti–Fortunato–Radicchi benchmark. Our results show our non-hierarchical method outperforms a known hierarchical fuzzy clustering method, and also performs better than a well-known membership-based modularity function. Our method proved to perform beyond satisfactory for both assortative and disassortative networks.
-  M. E. J. Newman, “Networks: An Introduction,” Oxford University Press, 2010.
-  S. Fortunato, “Community detection in graphs,” Physics Reports, Vol.486, pp. 75-174, 2010.
-  F. D. Malliaros and M. Vazirgiannis, “Clustering and community detection in directed networks: A survey,” Physics Reports, Vol.533, pp. 95-142, 2013.
-  S. Fortunato and D. Hric, “Community detection in networks: A user guide,” Physics Reports, Vol.659, pp. 1-44, 2016.
-  M. E. J. Newman, “Assortative mixing in networks,” Pysical Review Letters, Vol.89, No.20, Article No.208701, 2002.
-  T. Tanizawa, S. Havlin, and H. E. Stanley, “Robustness of onionlike correlated networks against targeted attacks,” Physical Review E, Vol.85, Article No.046109, 2012.
-  M. E. J. Newman, “Mixing patterns in networks,” Physical Review E, Vol.67, Article No.026126, 2003.
-  H.-B. Hu and X.-F. Wang, “Disassortative mixing in online social networks,” Europhysics Letters, Vol.86, No.1, Article No.18003, 2009.
-  L. Šubelj and M. Bajec, “Clustering assortativity, communities and functional modules in real-world networks,” arXiv preprint, arXiv:1202.3188, 2012.
-  R. Kojima and T. Murofushi, “Fuzzy clustering for scale-free network represented as adjacency matrix,” J. of Japan Society for Fuzzy Theory and Intelligent Informatics, Vol.29, No.5, pp. 645-650, 2017 (in Japanese with English abstract).
-  M. E. J. Newman, “Modularity and community structure in networks,” Proc. of the National Academy of Sciences (PNAS), Vol.103, No.23, pp. 8577-8582, 2006.
-  S. Wasserman and K. Faust, “Social Network Analysis Methods and Applications,” Cambridge University Press, 1994.
-  A. Lancichinetti, S. Fortunato, and J. Kertész, “Detecting the overlapping and hierarchical community structure in complex networks,” New J. of Physics, Vol.11, 2009.
-  J. Xu, J. Han, K. Xiong, and F. Nie, “Robust and sparse fuzzy k-means clustering,” Proc. of the 25th Int. Joint Conf. on Artificial Intelligence (IJCAI 2016), pp. 2224-2230, 2016.
-  Z. Ahmed and S. Kumar, “Pearson’s correlation coefficient in the theory of networks: A comment,” arXiv preprint, arXiv:1803.06937, 2018.
-  P. Bonacich, “Power and centrality: A family of measures,” American J. of Sociology, Vol.92, No.5, pp. 1170-1182, 1987.
-  A. Gulyás, J. J. Bíró, A. Kőrösi, G. Rétvári, and D. Krioukov, “Navigable networks as Nash equilibria of navigation games,” Nature Communications, Vol.6, Article No.7651, 2015.
-  M. E. J. Newman and M. Girvan, “Finding and evaluating community structure in networks,” Physical Review E, Vol.69, Article No.026113, 2004.
-  N. Tamás, P. Andrea, N. László, and B. Fülöp, “Fuzzy communities and the concept of bridgeness in complex networks,” Physical Review E, Vol.77, Article No.016107, 2008.
-  S. Zhang, R.-S. Wang, and X.-S. Zhang, “Identification of overlapping community structure in complex networks using fuzzy c-means clustering,” Physica A, Vol.374, pp. 483-490, 2007.
-  A. Lancichinetti and S. Fortunato, “Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities,” Physical Review E, Vol.80, Article No.016118, 2009.
-  E. Becker, B. Robisson, C. E. Chapple, A. Guénoche, and C. Brun, “Multifunctional proteins revealed by overlapping clustering in protein interaction network,” Bioinformatics, Vol.28, No.1, pp. 84-90, 2012.
-  J. M. Kleinberg, “Navigation in a small world,” Nature, Vol.406, Article No.845, 2000.
-  J. Fagnan, A. Abnar, R. Rabbany, and O. R. Zaiane, “Modular Networks for Validating Community Detection Algorithms,” arXiv preprint, arXiv:1801.01229, 2018.
-  V. D. Blondel, J. L. Guillaume, R. Lambiotte, and E. Lefebvre, “Fast unfolding of communities in large networks,” J. of Statistical Mechanics: Theory and Experiment, Vol.2008, No.10, pp. 1-12, 2008.
This article is published under a Creative Commons Attribution-NoDerivatives 4.0 Internationa License.