×

zbMATH — the first resource for mathematics

Graph clustering via intra-cluster density maximization. (English) Zbl 1443.91245
Bychkov, Ilya (ed.) et al., Network algorithms, data mining, and applications. NET 2018, Moscow, Russia, May 18–19, 2018. Proceedings of the 8th international conference on network analysis. Cham: Springer. Springer Proc. Math. Stat. 315, 37-48 (2020).
Summary: Graph clustering, also often referred to as network community detection, is the process of assigning common labels to vertices that are densely connected to each other but sparsely connected to the rest of the graph. There are many different approaches to clustering in the literature. However, in this article, we formulate the clustering problem as a combinatorial optimization problem. Our main contribution is a novel problem formulation that maximizes intra-cluster density, a statistically meaningful quantity. It requires the number of clusters, a softbound on cluster size and a penalty coefficient as parameter inputs. More importantly, it is designed to prevent common degeneracies, like the so-called “mega-clusters”. We end with some suggestions on numerical solution techniques and note that an ensemble-like optimization routine seems promising.
For the entire collection see [Zbl 1444.68005].
MSC:
91D30 Social networks; opinion dynamics
91C20 Clustering in the social and behavioral sciences
90C27 Combinatorial optimization
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aloise, D., Caporossi, G., Hansen, P., Liberti, L., Perron, S., Ruiz, M.: Modularity maximization in networks by variable neighborhood search. In: Bader, D.A., Meyerhenke, H., Sanders, P., Wagner, D. (eds.) Graph Partitioning and Graph Clustering, 10th DIMACS Implementation Challenge Workshop, Georgia Institute of Technology, Atlanta, GA, USA, 13-14 Feb 2012, pp. 113-128 (2012). http://www.ams.org/books/conm/588/11705 · Zbl 1276.90055
[2] Bertsimas, D., Tsitsiklis, J.: Simulated annealing. Stat. Sci. 8(1), 10-15 (1993) · Zbl 0764.60073
[3] Brownlee, J.: Clever Algorithms: Nature-Inspired Programming Recipes, 1st edn. Lulu.com (2011)
[4] Creusefond, J., Largillier, T., Peyronnet, S.: Finding compact communities in large graphs. In: Proceedings of the 2015 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining 2015, ASONAM ’15, pp. 1457-1464. ACM, New York, NY, USA (2015). https://doi.org/10.1145/2808797.2808868
[5] van Dongen, S.: Graph clustering by flow simulation. Ph.D. thesis, Faculteit Wiskunde en Informatica, Universiteit Utrecht (2000)
[6] Fan, N., Pardalos, P.M.: Linear and quadratic programming approaches for the general graph partitioning problem. J. Global Optim. 48(1), 57-71 (2010). https://doi.org/10.1007/s10898-009-9520-1 · Zbl 1202.90261
[7] Fan, N., Pardalos, P.M.: Robust optimization of graph partitioning and critical node detection in analyzing networks. In: Proceedings of the 4th International Conference on Combinatorial Optimization and Applications—Volume Part I, COCOA’10, pp. 170-183. Springer, Berlin, Heidelberg (2010). http://dl.acm.org/citation.cfm?id=1940390.1940405 · Zbl 1311.90163
[8] Fortunato, S.: Community detection in graphs. Phys. Rep. 486, 75-174 (2010). https://doi.org/10.1016/j.physrep.2009.11.002
[9] Fortunato, S., Barthélemy, M.: Resolution limit in community detection. Proc. Natl. Acad. Sci. 104(1), 36-41 (2007). http://www.pnas.org/content/104/1/36.abstract
[10] Fortunato, S., Hric, D.: Community detection in networks: a user guide. ArXiv e-prints (2016)
[11] Hastie, T., Tibshirani, R., Friedman, J.: The Elements of Statistical Learning, Second Edition: Data Mining, Inference, and Prediction, 2nd ed. Springer Series in Statistics. Springer (2009) · Zbl 1273.62005
[12] Holland, P.W., Laskey, K.B., Leinhardt, S.: Stochastic blockmodels: First steps. Soc. Netw. 5(2), 109-137 (1983). https://doi.org/10.1016/0378-8733(83)90021-7. http://www.sciencedirect.com/science/article/pii/0378873383900217
[13] Jin, J.: Fast community detection by score. Ann. Stat. 43 (2015) · Zbl 1310.62076
[14] Kazakovtsev, L., Antamoshkin, A.: Genetic algorithm with fast greedy heuristic for clustering and location problems. Informatica (Slovenia) 38(3) (2014). http://www.informatica.si/index.php/informatica/article/view/704
[15] Lancichinetti, A., Radicchi, F., Ramasco, J.J., Fortunato, S.: Finding statistically significant communities in networks. PLoS ONE 6, e18,961 (2011). https://doi.org/10.1371/journal.pone.0018961
[16] von Luxburg, U.: A Tutorial on Spectral Clustering. CoRR abs/0711.0189 (2007). http://arxiv.org/abs/0711.0189
[17] Miasnikof, P., Shestopaloff, A., Bonner, A., Lawryshyn, Y.: A statistical performance analysis of graph clustering algorithms. In: Lecture Notes in Computer Science. Springer (2018)
[18] Nascimento, M., Pitsoulis, L.: Community detection by modularity maximization using GRASP with path relinking. Comput. Oper. Res. 40, 3121-3131 (2013) · Zbl 1348.91237
[19] Newman, M.E.J., Girvan, M.: Finding and evaluating community structure in networks. Phys. Rev. E, Stat. Nonlinear, Soft Matter Phys. 69, 026,113 (2004)
[20] Ovelgönne, M., Geyer-Schulz, A.: An ensemble learning strategy for graph clustering. In: Bader, D.A., Meyerhenke, H., Sanders, P., Wagner, D. (eds.) Graph Partitioning and Graph Clustering, 10th DIMACS Implementation Challenge Workshop, Georgia Institute of Technology, Atlanta, GA, USA, 13-14 Feb 2012, pp. 113-128 (2012). http://www.ams.org/books/conm/588/11705
[21] Papadimitriou, C., Steiglitz, K.: Combinatorial Optimization: Algorithms and Complexity. Dover Books on Computer Science. Dover Publications (1998). https://books.google.ca/books?id=u1RmDoJqkF4C · Zbl 0944.90066
[22] Prokhorenkova, L.O., Prałat, P., Raigorodskii, A.: Modularity of complex networks models. In: Bonato, A., Graham, F., Prałat, P. (eds.) Algorithms and Models for the Web Graph, pp. 115-126. Springer International Publishing, Cham (2016) · Zbl 1398.05188
[23] Prokhorenkova, L.O., Prałat, P., Raigorodskii, A.: Modularity in several random graph models. In: The European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB’17), Electronic Notes in Discrete Mathematics 61, 947-953 (2017). https://doi.org/10.1016/j.endm.2017.07.058. http://www.sciencedirect.com/science/article/pii/S1571065317302238 · Zbl 1378.05187
[24] Russell, S., Norvig, P.: Artificial Intelligence: A Modern Approach, pp. 92-115. Prentice-Hall Inc. (1995) · Zbl 0835.68093
[25] Schaeffer, S.E.: Survey: graph clustering. Comput. Sci. Rev. 1(1), 27-64 (2007). https://doi.org/10.1016/j.cosrev.2007.05.001 · Zbl 1302.68237
[26] Tasgin, M., Herdagdelen, A., Bingol, H.: Community Detection in Complex Networks Using Genetic Algorithms. ArXiv e-prints (2007)
[27] Weisstein, E.: Clique. MathWorld-A Wolfram Web Resource (2018). http://mathworld.wolfram.com/Clique.html
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.