Dense and sparse graph partition. (English) Zbl 1252.05172
Summary: In a graph \(G=(V,E)\), the density is the ratio between the number of edges \(|E|\) and the number of vertices \(|V|\). This criterion may be used to find communities in a graph: groups of highly connected vertices. We propose an optimization problem based on this criterion; the idea is to find the vertex partition that maximizes the sum of the densities of each class. We prove that this problem is NP-hard by giving a reduction from graph-\(k\)-colorability. Additionally, we give a polynomial time algorithm for the special case of trees.
MSC:
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
| 05C42 | Density (toughness, etc.) |
| 05C40 | Connectivity |
| 05C82 | Small world graphs, complex networks (graph-theoretic aspects) |
Software:
GraclusReferences:
| [1] | Aloise, D.; Deshpande, A.; Hansen, P.; Popat, P., NP-hardness of euclidean sum-of-squares clustering, Machine Learning, 75, 2, 245-248 (2009) · Zbl 1378.68047 |
| [2] | Ausiello, G.; Protasi, M.; Marchetti-Spaccamela, A.; Gambosi, G.; Crescenzi, P.; Kann, V., Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties (1999), Springer-Verlag New York, Inc.: Springer-Verlag New York, Inc. Secaucus, NJ, USA · Zbl 0937.68002 |
| [3] | Boros, E.; Hammer, P. L.; Ibaraki, T.; Kogan, A.; Mayoraz, E.; Muchnik, I., An implementation of logical analysis of data, IEEE Transactions on Knowledge and Data Engineering, 12, 2, 292-306 (2000) |
| [4] | Brandes, U., A faster algorithm for betweenness centrality, Journal of Mathematical Sociology, 25, 163-177 (2001) · Zbl 1051.91088 |
| [5] | Brusco, M.; Stahl, S., Branch-and-Bound Applications in Combinatorial Data Analysis (2005), Springer · Zbl 1093.62006 |
| [6] | M. Charikar, Greedy approximation algorithms for finding dense components in a graph, in: APPROX, 2000, pp. 84-95.; M. Charikar, Greedy approximation algorithms for finding dense components in a graph, in: APPROX, 2000, pp. 84-95. · Zbl 0976.05062 |
| [7] | Clauset, A.; Moore, C.; Newman, M. E.J., Hierarchical structure and the prediction of missing links in networks, Nature, 453, 98-101 (2008) |
| [8] | J. Darlay, Analyse Combinatoire de données: Structure et Optimisation. Ph.D. Thesis, Université de Grenoble, 2011.; J. Darlay, Analyse Combinatoire de données: Structure et Optimisation. Ph.D. Thesis, Université de Grenoble, 2011. |
| [9] | S. Dasgupta, The hardness of \(k\); S. Dasgupta, The hardness of \(k\) |
| [10] | Dhillon, I.; Guan, Y.; Kulis, B., Weighted graph cuts without eigenvectors: a multilevel approach, IEEE Transactions on Pattern Analysis and Machine Intelligence, 29, 11, 1944-1957 (2007) |
| [11] | Diestel, R., (Graph Theory. Graph Theory, Graduate Texts in Mathematics, vol. 173 (2005), Springer-Verlag: Springer-Verlag Heidelberg) · Zbl 1074.05001 |
| [12] | Feder, T.; Hell, P.; Klein, S.; Motwani, R., List partitions, SIAM J. Discrete Math., 16, 3, 449-478 (2003) · Zbl 1029.05143 |
| [13] | Feige, U.; Kortsarz, G.; Peleg, D., The dense \(k\)-subgraph problem, Algorithmica, 29, 2001 (1999) · Zbl 0969.68117 |
| [14] | Fortunato, S., Community detection in graphs, Physics Reports, 486, 3-5, 75-174 (2010) |
| [15] | Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (Series of Books in the Mathematical Sciences) (1979), W.H. Freeman & Co. Ltd. · Zbl 0411.68039 |
| [16] | A.V. Goldberg, Finding a maximum density subgraph. Technical Report UCB/CSD-84-171, EECS Department, University of California, Berkeley, 1984.; A.V. Goldberg, Finding a maximum density subgraph. Technical Report UCB/CSD-84-171, EECS Department, University of California, Berkeley, 1984. |
| [17] | Gulbahce, N.; Lehmann, S., The art of community detection, BioEssays, 30, 934-938 (2008) |
| [18] | Kleinberg, J., An impossibility theorem for clustering, Advances in Neural Information Processing Systems (2002) |
| [19] | König, D., Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre, Mathematische Annalen, 77, 453-465 (1916), (in German) · JFM 46.0146.03 |
| [20] | Maravalle, M.; Simeone, B.; Naldini, R., Clustering on trees, Computational Statistics & Data Analysis, 24, 2, 217-234 (1997) · Zbl 0900.62327 |
| [21] | Newman, M. E.J., Detecting community structure in networks, The European Physical Journal B — Condensed Matter and Complex Systems, 38, 2, 321-330 (2004) |
| [22] | Newman, M. E.J.; Girvan, M., Finding and evaluating community structure in networks, Physical Review E, 69, 026113 (2004) |
| [23] | Schaeffer, S., Graph clustering, Computer Science Review, 1, 1, 27-64 (2007) · Zbl 1302.68237 |
| [24] | Schrijver, A., Combinatorial Optimization: Polyhedra and Efficiency (2003), Springer · Zbl 1041.90001 |
| [25] | Scott, J. P., Social Network Analysis: A Handbook (2000), SAGE Publications |
| [26] | Shi, J.; Malik, J., Normalized cuts and image segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, 22, 8, 888-905 (2000) |
| [27] | Síma, J.; Schaeffer, S. E., On the NP-completeness of some graph cluster measures, (SOFSEM 2006: Theory and Practice of Computer Science. SOFSEM 2006: Theory and Practice of Computer Science, Lecture Notes in Computer Science, vol. 3831 (2006)), 530-537 · Zbl 1175.68284 |
| [28] | Witten, I. H.; Frank, E., (Data Mining: Practical Machine Learning Tools and Techniques with Java Implementations. Data Mining: Practical Machine Learning Tools and Techniques with Java Implementations, The Morgan Kaufmann Series in Data Management Systems (1999), Morgan Kaufmann) |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
