Top

Journal of Classification

Published in:

06-07-2022

Community Detection in Feature-Rich Networks Using Data Recovery Approach

Authors: Boris Mirkin, Soroosh Shalileh

Published in: Journal of Classification | Issue 3/2022

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

The problem of community detection in a network with features at its nodes takes into account both the graph structure and node features. The goal is to find relatively dense groups of interconnected entities sharing some features in common. There have been several approaches proposed for that. We apply the so-called data recovery approach to the problem by combining the least-squares recovery criteria for both the graph structure and node features. In this way, we obtain a new clustering criterion and a corresponding algorithm for finding clusters one-by-one. We show that our proposed method is effective on real-world data, as well as on synthetic data involving either only quantitative features or only categorical attributes or both. In the cases at which attributes are categorical, state-of-the-art algorithms are available. Our algorithm appears competitive against them.

previous article Network-Based Discriminant Analysis for Multiclassification

next article Finite Mixture of Censored Linear Mixed Models for Irregularly Observed Longitudinal Data

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Abrahao, B., Soundarajan, S., Hopcroft, J., & Kleinberg, R. (2012). On the separability of structural classes of communities. Proceedings of the 18th ACM SIGKDD international conference on knowledge discovery and data mining proceedings of the 18th ACM SIGKDD international conference on knowledge discovery and data mining (pp. 624–632).

Abu-El-Haija Alipourfard, S., Harutyunyan, N., Kapoor, H., & Perozzi, B. A. (2018). Higher-order graph convolutional layer. Proceedings of the 32nd conference on neural information processing systems (NIPS) (pp. 1–6).

Amorim, R., & Mirkin, B. (2012). Feature weighting and anomalous cluster initializing in k-means clustering minkowski metric. Pattern Recognition, 45(3), 1061–1075.CrossRef

Blondel, V., Guillaume, J., Lambiotte, R., & Lefebvre, E. (2008). Fast unfolding of communities in large networks. Journal of Statistical Mechanics: Theory and Experiment, P10008(10), 12–20.MATH

Bojchevski, A. & Günnemanz, S. (2018). Bayesian robust attributed graph clustering: Joint learning of partial anomalies and group structure. Thirty-second AAAI conference on artificial intelligence (pp. 12–20).

Boyd, S., & Vandenberghe, L. (2004). Convex optimization (1st ed.). Cambridge: Cambridge University Press.CrossRefMATH

Chang, S., Han, W., Tang, J., Qi, G., Aggarwal, C., & Huang, T. (2015). Heterogeneous network embedding via deep architectures. Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining (pp. 119–128).

Cheng, H., Zhou, Y., & Yu, J. (2011). Clustering large attributed graphs: A balance between structural and attribute similarities. ACM Transactions on Knowledge Discovery from Data (TKDD), 5(2), 1–33.MathSciNetCrossRef

Cheng, Y. Z. H. & Yu, J. (2010). Clustering large attributed graphs: An efficient incremental approach. IEEE international conference on data mining (pp. 689–698).

Chiang, M., & Mirkin, B. (2010). Intelligent choice of the number of clusters in k-means clustering: an experimental study with different cluster spreads. Journal of Classification, 27(1), 3–40.MathSciNetCrossRefMATH

Chunaev, P. (2020). Community detection in node-attributed social networks: a survey. Computer Science Review, 100286(37), 1–24.MathSciNetMATH

Citraro, S., & Rossetti, G. (2020). Identifying and exploiting homogeneous communities in labeled networks. Applied Network Science, 5(1), 1–203.CrossRef

Cover, T., & Thomas, J. (2006). Elements of information theory. New York: John Wiley and Sons.MATH

Cross, R., & Parker, A. (2004). The hidden power of social networks: Understanding how work really gets done in organizations. Cambridge: Harvard Business Press.

Cruz, J., Bothorel, C. & Poulet, F. (2011). Entropy based community detection in augmented social networks. International conference on computational aspects of social networks (CASoN) (pp. 163–168). IEEE

Dang, T., & Viennet, E. (2012). Community detection based on structural and attribute similarities. International conference on digital society (pp. 7–12).

Decelle, A., Krzakala, F., Moore, C., & Zdeborova, L. (2011). Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications. Physical Review, 84(6), E066106.

Depril, D., Mechelen, I. V., & Mirkin, B. (2008). Algorithms for additive clustering of rectangular data tables. Computational Statistics & Data Analysis, 52(11), 4923–4938.MathSciNetCrossRefMATH

Gao, C., & Ma, Z. (2021). Minimax rates in network analysis: Graphon estimation, community detection and hypothesis testing. Statistical Science, 36(1), 16–33.MathSciNetCrossRefMATH

Gaucher, S., & Klopp, O. (2019). Maximum likelihood estimation of sparse networks with missing observations. arXiv:1902.10605

Green, P., & Silverman, B. (1993). Nonparametric regression and generalized linear models: a roughness penalty approach (1st ed.). USA: Chapman and Hall/CRC.CrossRefMATH

He, D., Jin, D., Chen, Z., & Zhang, W. (2015). Identification of hybrid node and link communities in complex networks. Nature Scientific Reports, 8638.

Holland, P., Laskey, K., & Leinhardt, S. (1983). Stochastic blockmodels: First steps. Social Networks, 5(2), 109–137.MathSciNetCrossRef

Hu, Y., Li, M., Zhang, P., Fan, Y., & Di, Z. (2008). Community detection by signaling on complex networks. Physical Review E, 78(1), 16115.CrossRef

Hubert, L., & Arabie, P. (1985). Comparing partitions. Journal of Classification, 2(1), 193–218.CrossRefMATH

Interdonato, R., Atzmueller, M., Gaito, S., Kanawati, R., Largeron, C., & Sala, A. (2019). Feature-rich networks: going beyond complex network topologies. Applied Network Science, 4(1), 1–13.CrossRef

Jia, C., Li, Y., Carson, M., Wang, X., & Yu, J. (2017). Node attribute-enhanced community detection in complex networks. Scientific Reports, 7(1), 2626.CrossRef

Jin, H., Yu, W., & Li, S. (2018). A clustering algorithm for determining community structure in complex networks. Physica A: Statistical Mechanics and its Applications, 492, 980–993.CrossRefMATH

Karger, D. (1993). Global min-cuts in rnc, and other ramifications of a simple min-cut algorithm. SODA (pp. 21–30).

Kovaleva, E., & Mirkin, B. (2015). Bisecting k-means and 1d projection divisive clustering: A unified framework and experimental comparison. Journal of Classification, 32(3), 414–442.MathSciNetCrossRefMATH

Larremore, D. B., Clauset, A., & Buckee, C. O. (2013). Network approach to analyzing highly recombinant malaria parasite genes. PLoS Computational Biology, 9(10), e1003268.CrossRef

Lazega, E. (2001). The collegial phenomenon: The social mechanisms of cooperation among peers in a corporate law partnership. New York: Oxford University Press.CrossRef

Leskovec, J. & Sosič, R. (2016). Snap: A general-purpose network analysis and graph-mining library. ACM Transactions on Intelligent Systems and Technology (TIST), 8(1), 1–20. https://github.com/snap-stanford/snap/tree/master/examples/cesna. Accessed 23 July 2021.

Li, J., Rong, Y., Cheng, H., Meng, H., Huang, W. & Huang, J. (2019). Semi-supervised graph classification: A hierarchical graph perspective. The World Wide Web conference(ACM) (pp. 972–982).

Li, Y., Jia, C., & Yu, J. (2015). Parameter-free community detection method based on centrality and dispersion of nodes in complex networks. Physica A-Statistical Mechanics and Its Applications, 438, 321–334.CrossRef

Mirkin, B. (1987). Additive clustering and qualitative factor analysis methods for similarity matrices. Journal of Classification, 4(1), 7–31.MathSciNetCrossRefMATH

Mirkin, B. (2012). Clustering: A data recovery approach (2nd ed.). Boca Raton: CRC Press.MATH

Mirkin, B., & Nascimento, S. (2012). Additive spectral method for fuzzy cluster analysis of similarity data including community structure and affinity matrices. Information Sciences, 183(1), 16–34.CrossRef

Monge, A., & Elkan, C. (1997). An efficient domain-independent algorithm for detecting approximately duplicate database records.

Neville, J., Adler, M., & Jensen, D. (2003). Clustering relational data using attribute and link information. Proceedings of the text mining and link analysis workshop, 18th international joint conference on artificial intelligence (pp. 9–15).

Newman, M. (2006). Modularity and community structure in networks. Proceedings of the National Academy of Sciences, 103(23), 8577–8582.CrossRef

Newman, M. J. (2016). Washington, D.C. University. SIAN source file: https://www.nature.com/articles/ncomms11863. Accessed 23 July 2021.

Newman, M., & Clauset, A. (2016). Structure and inference in annotated networks. Nature Communications, 7(1), 1–11.CrossRef

Ng, A. (2011). Sparse autoencoder cs294a lecture notes 72.2011, pp. 1–19. https://web.stanford.edu/class/cs294a/sparseAutoencoder_2011new.pdf. Accessed 23 July 2021.

Nooy, W. D., Mrvar, A., & Batagelj, V. (2004). Exploratory social network analysis with pajek. Cambridge: Cambridge University Press.

Nowicki, K., & Snijders, T. (2001). Estimation and prediction for stochastic blockstructures. Journal of the American Statistical Association, 96(455), 1077–1087.MathSciNetCrossRefMATH

Page, L., & S.B.R.M.T.W. (1999). Pagerank citation ranking: bringing order to the web. Technical Report, Stanford InfoLab.

Peel, L., Larremore, D., & Clauset, A. (2017). The ground truth about metadata and community detection in networks. Science Advances, 3(5), e1602548.CrossRef

Raghavan, U., Albert, R., & Kumara, S. (2007). Near linear time algorithm to detect community structures in large-scale networks. Physical Review E, 76(3), 036106.CrossRef

Rossetti, G. (2020). Eva source file. https://github.com/GiulioRossetti/EVA. Accessed 23 July 2021.

Shi, J., & Malik, J. (2000). Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(8), 888–905.CrossRef

Shi, W., Huang, L., Li, J. H., Wang, C., Tang, Y., & Fu, C. (2019). Network embedding via community based variational autoencoder. IEEE Access, 7, 25323–25333.CrossRef

Snijders, T. (2001). Lawyers data set. https://www.stats.ox.ac.uk/~snijders/siena/Lazega_lawyers_data.htm. Accessed 23 July 2021.

Stanley, N., Bonacci, T., Kwitt, R., Niethammer, M., & Mucha, P. (2019). Stochastic block models with multiple continuous attributes. Applied Network Science, 4(1), 1–22.CrossRef

Steinhaeuser, K., & Chawla, N. (2008). Community detection in a large real-world social network. In social computing, behavioral modeling, and prediction (pp. 168–175).

Wang, D., & Zhao, Y. (2019). Network community detection from the perspective of time series. Physica A: Statistical Mechanics and its Applications, 522, 205–214.CrossRef

Xu, Z., Ke, Y., Wang, Y., Cheng, H., & Cheng, J. (2012). A model-based approach to attributed graph clustering. Proceedings of the 2012 ACM SIGMOD international conference on management of data (pp. 505–516). ACM

Yang, J., McAuley, J., & Leskovec, J. (2013). Community detection in networks with node attributes. IEEE 13th international conference on data mining (pp. 1151–1156).

Yin, Z., Gupta, M., Weninger, T., & Han, J. (2010). A unified framework for link recommendation using random walks. 2010 international conference on advances in social networks analysis and mining (pp. 152–159). IEEE

Zhang, Y., Levina, E., & Zhu, J. (2016). Community detection in networks with node features. Electronic Journal of Statistics, 10(2), 3153–3178.MathSciNetCrossRefMATH

Title: Community Detection in Feature-Rich Networks Using Data Recovery Approach
Authors: Boris Mirkin
Soroosh Shalileh
Publication date: 06-07-2022
Publisher: Springer US
Published in: Journal of Classification / Issue 3/2022
Print ISSN: 0176-4268
Electronic ISSN: 1432-1343
DOI: https://doi.org/10.1007/s00357-022-09416-w

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 3/2022

Group-Wise Shrinkage Estimation in Penalized Model-Based Clustering

Network-Based Discriminant Analysis for Multiclassification

Multinomial Principal Component Logistic Regression on Shape Data

Hierarchical Means Clustering

Understanding the Adjusted Rand Index and Other Partition Comparison Indices Based on Counting Object Pairs

Infinite Mixtures of Multivariate Normal-Inverse Gaussian Distributions for Clustering of Skewed Data

Premium Partner