More Web Proxy on the site http://driver.im/

article

Free access

Axioms for graph clustering quality functions

Editors: Kevin Murphy, Bernhard Schölkopf Authors:

Twan Van Laarhoven,

Elena MarchioriAuthors Info & Claims

The Journal of Machine Learning Research, Volume 15, Issue 1

Pages 193 - 215

Published: 01 January 2014 Publication History

PDF eReader Publisher Site

Abstract

We investigate properties that intuitively ought to be satisfied by graph clustering quality functions, that is, functions that assign a score to a clustering of a graph. Graph clustering, also known as network community detection, is often performed by optimizing such a function. Two axioms tailored for graph clustering quality functions are introduced, and the four axioms introduced in previous work on distance based clustering are reformulated and generalized for the graph setting. We show that modularity, a standard quality function for graph clustering, does not satisfy all of these six properties. This motivates the derivation of a new family of quality functions, adaptive scale modularity, which does satisfy the proposed axioms. Adaptive scale modularity has two parameters, which give greater flexibility in the kinds of clusterings that can be found. Standard graph clustering quality functions, such as normalized cut and unnormalized cut, are obtained as special cases of adaptive scale modularity.

In general, the results of our investigation indicate that the considered axiomatic framework covers existing 'good' quality functions for graph clustering, and can be used to derive an interesting new family of quality functions.

References

[1]

Margareta Ackerman and Shai Ben-David. Measures of clustering quality: A working set of axioms for clustering. In Daphne Koller, Dale Schuurmans, Yoshua Bengio, and Léon Bottou, editors, NIPS, pages 121-128. Curran Associates, Inc., 2008.

[2]

Margareta Ackerman and Shai Ben-David. A characterization of linkage-based hierarchical clustering. Journal of Machine Learning Research, 2013.

[3]

Margareta Ackerman, Shai Ben-David, and David Loker. Towards property-based classification of clustering paradigms. In John D. Lafferty, Christopher K. I. Williams, John Shawe-Taylor, Richard S. Zemel, and Aron Culotta, editors, NIPS, pages 10-18. Curran Associates, Inc., 2010a.

[4]

Margareta Ackerman, Shai Ben-David, and David Loker. Characterization of linkage-based clustering. In Adam Tauman Kalai and Mehryar Mohri, editors, COLT, pages 270-281. Omnipress, 2010b. ISBN 978-0-9822529-2-5.

[5]

Margareta Ackerman, Shai Ben-David, Simina Brânzei, and David Loker. Weighted clustering. In Jörg Hoffmann and Bart Selman, editors, AAAI. AAAI Press, 2012.

[6]

Margareta Ackerman, Shai Ben-David, David Loker, and Sivan Sabato. Clustering oligarchies. In Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS), volume 31 of JMLR Workshop and Conference Proceedings, pages 66-74, 2013.

[7]

Helio Almeida, Dorgival Guedes, Wagner Meira Jr., and Mohammed J. Zaki. Is there a best quality metric for graph clusters? In Dimitrios Gunopulos, Thomas Hofmann, Donato Malerba, and Michalis Vazirgiannis, editors, Machine Learning and Knowledge Discovery in Databases, volume 6911 of Lecture Notes in Computer Science, pages 44-59. Springer Berlin Heidelberg, 2011. ISBN 978-3-642-23779-9.

Digital Library

[8]

Vincent D. Blondel, Jean-Loup Guillaume, Renaud Lambiotte, and Etienne Lefebvre. Fast unfolding of communities in large networks. J. Stat. Mech. Theory Exp., 2008(10):P10008, 2008. ISSN 1742-5468. URL http://dx.doi. org/10.1088/1742-5468/2008/10/P10008.

[9]

Béla Bollobás. The Evolution of Random Graphs - the Giant Component, pages 130-159. Cambridge University Press, 2001. ISBN 9780521797221.

[10]

Ulrik Brandes, Daniel Delling, Marco Gaertler, Robert Gorke, Martin Hoefer, Zoran Nikoloski, and Dorothea Wagner. On modularity clustering. IEEE Transactions on Knowledge and Data Engineering, 20(2):172-188, 2008. ISSN 1041-4347.

Digital Library

[11]

Sébastien Bubeck and Ulrike von Luxburg. Nearest neighbor clustering: A baseline method for consistent clustering with arbitrary objective functions. J. Mach. Learn. Res., 10: 657-698, June 2009. ISSN 1532-4435. URL http://dl.acm.org/citation.cfm?id=1577069.1577092.

Digital Library

[12]

Gunnar Carlsson, Facundo Mémoli, Alejandro Ribeiro, and Santiago Segarra. Axiomatic construction of hierarchical clustering in asymmetric networks. CoRR, abs/1301.7724, 2013.

[13]

Thang N. Dinh and My T. Thai. Community detection in scale-free networks: Approximation algorithms for maximizing modularity. IEEE Journal on Selected Areas in Communications, 31(6):997-1006, 2013.

[14]

Santo Fortunato and Marc Barthélemy. Resolution limit in community detection. Proc. Natl. Acad. Sci. USA, 104(1):36-41, 2007.

[15]

Sreenivas Gollapudi and Aneesh Sharma. An axiomatic approach for result diversification. In Proceedings of the 18th International Conference on World Wide Web, pages 381-390, 2009.

Digital Library

[16]

Benjamin H. Good, Yves A. de Montjoye, and Aaron Clauset. Performance of modularity maximization in practical contexts. Phys. Rev. E, 81(4):046106, April 2010. 1103/PhysRevE.81.046106. URL http://dx.doi.org/10.1103/PhysRevE.81.046106.

[17]

Jon M. Kleinberg. An impossibility theorem for clustering. In Suzanna Becker, Sebastian Thrun, and Klaus Obermayer, editors, NIPS, pages 446-453. MIT Press, 2002. ISBN 0-262-02550-7.

[18]

Andrea Lancichinetti and Santo Fortunato. Limits of modularity maximization in community detection. Phys. Rev. E, 84:066122, December 2011. URL http://dx.doi.org/10.1103/PhysRevE.84.066122.

[19]

Marina Meila. Comparing clusterings: an axiomatic view. In Proceedings of the 22nd International Conference on Machine Learning, pages 577-584. ACM, 2005.

Digital Library

[20]

Mark E. J. Newman. Finding community structure in networks using the eigenvectors of matrices. Phys. Rev. E, 74(3):036104, July 2006. URL http://dx.doi.org/10.1103/PhysRevE.74.036104.

[21]

Mark E. J. Newman and Michelle Girvan. Finding and evaluating community structure in networks. Phys. Rev. E, 69:026113, Feb 2004. URL http://pre.aps.org/abstract/PRE/v69/i2/e026113.

[22]

Jan Puzicha, Thomas Hofmann, and Joachim M. Buhmann. A theory of proximity based clustering: Structure detection by optimization. Pattern Recognition, 33:617-634, 1999.

[23]

Jörg Reichardt and Stefan Bornholdt. Detecting fuzzy community structures in complex networks with a Potts model. Phys. Rev. Lett., 93:218701, 2004.

[24]

Jörg Reichardt and Stefan Bornholdt. Statistical mechanics of community detection. Physical Review E, 74(1):016110, 2006.

[25]

Jörg Reichardt and Stefan Bornholdt. Partitioning and modularity of graphs with arbitrary degree distribution. Phys. Rev. E, 76:015102, Jul 2007. URL http://link.aps.org/doi/10.1103/PhysRevE.76.015102.

[26]

Jianhua Ruan and Weixiong Zhang. Identifying network communities with a high resolution. Phys. Rev. E, 77:016104, Jan 2008. URL http://link.aps.org/doi/10.1103/PhysRevE.77.016104.

[27]

Jianbo Shi and Jitendra Malik. Normalized cuts and image segmentation. volume 22, pages 888-905, Washington, DC, USA, August 2000. IEEE Computer Society. URL http://dx.doi.org/10.1109/34.868688.

Digital Library

[28]

Vincent A. Traag, Paul Van Dooren, and Yurii E. Nesterov. Narrow scope for resolution-limit-free community detection. Phys. Rev. E, 84:016114, Jul 2011. URL http://link.aps.org/doi/10.1103/PhysRevE.84.016114.

[29]

Vincent A. Traag, Gautier Krings, and Paul Van Dooren. Significant scales in community structure. Submitted, Jun 2013. URL http://arxiv.org/abs/1306.3398.

[30]

Twan van Laarhoven and Elena Marchiori. Graph clustering with local search optimization: The resolution bias of the objective function matters most. Phys. Rev. E, 87:012812, Jan 2013. URL http://link.aps.org/doi/10.1103/PhysRevE.87.012812.

[31]

Reza Bosagh Zadeh and Shai Ben-David. A uniqueness theorem for clustering. In Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence, UAI '09, pages 639-646, Arlington, Virginia, United States, 2009. AUAI Press. ISBN 978-0-9749039-5-8. URL http://dl.acm.org/citation.cfm?id=1795114.1795189.

Digital Library

Cited By

Kłopotek MKłopotek R(2023)On the Discrepancy between Kleinberg’s Clustering Axioms and k-Means Clustering Algorithm BehaviorMachine Language10.1007/s10994-023-06308-x112:7(2501-2553)Online publication date: 1-Mar-2023
https://dl.acm.org/doi/10.1007/s10994-023-06308-x
Kłopotek MKłopotek R(2022)Towards continuous consistency axiomApplied Intelligence10.1007/s10489-022-03710-153:5(5635-5663)Online publication date: 30-Jun-2022
https://dl.acm.org/doi/10.1007/s10489-022-03710-1
Kłopotek MKłopotek R(2022)Richness FallacyFoundations of Intelligent Systems10.1007/978-3-031-16564-1_25(262-271)Online publication date: 3-Oct-2022
https://dl.acm.org/doi/10.1007/978-3-031-16564-1_25
Show More Cited By

Axioms for graph clustering quality functions
1. Computing methodologies
  1. Machine learning
    1. Learning paradigms
      1. Unsupervised learning

Recommendations

Scalable and Accurate Graph Clustering and Community Structure Detection

One of the most useful measures of cluster quality is the modularity of the partition, which measures the difference between the number of the edges joining vertices from the same cluster and the expected number of such edges in a random graph. In this ...
Graph Clustering by Maximizing Statistical Association Measures
IDA 2013: Proceedings of the 12th International Symposium on Advances in Intelligent Data Analysis XII - Volume 8207

We are interested in objective functions for clustering undirected and unweighted graphs. Our goal is to define alternatives to the popular modularity measure. To this end, we propose to adapt statistical association coefficients, which traditionally ...
Graph clustering based on optimization of a macroscopic structure of clusters
DS'11: Proceedings of the 14th international conference on Discovery science

A graph is a flexible data structure for various data, such as the Web, SNSs and molecular architectures. Not only the data expressed naturally by a graph, it is also used for data which does not have explicit graph structures by extracting implicit ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image The Journal of Machine Learning Research

The Journal of Machine Learning Research Volume 15, Issue 1

January 2014

4085 pages

ISSN:1532-4435

EISSN:1533-7928

Editors:
Kevin Murphy
Google
,
Bernhard Schölkopf

Issue’s Table of Contents

Publisher

JMLR.org

Publication History

Published: 01 January 2014

Revised: 01 November 2013

Published in JMLR Volume 15, Issue 1

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
Total Citations
View Citations
224
Total Downloads

Downloads (Last 12 months)52
Downloads (Last 6 weeks)5

Reflects downloads up to 24 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Kłopotek MKłopotek R(2023)On the Discrepancy between Kleinberg’s Clustering Axioms and k-Means Clustering Algorithm BehaviorMachine Language10.1007/s10994-023-06308-x112:7(2501-2553)Online publication date: 1-Mar-2023
Kłopotek MKłopotek R(2022)Towards continuous consistency axiomApplied Intelligence10.1007/s10489-022-03710-153:5(5635-5663)Online publication date: 30-Jun-2022
Kłopotek MKłopotek R(2022)Richness FallacyFoundations of Intelligent Systems10.1007/978-3-031-16564-1_25(262-271)Online publication date: 3-Oct-2022
Estes ABall MLovell D(2021)Data Exploration by Representative Region SelectionMathematics of Operations Research10.1287/moor.2020.111546:3(970-1007)Online publication date: 1-Aug-2021
Kłopotek MKłopotek R(2021)Issues in clustering algorithm consistency in fixed dimensional spaces. Some solutions for k-meansJournal of Intelligent Information Systems10.1007/s10844-021-00657-657:3(509-530)Online publication date: 1-Dec-2021
Beer AHartmann VSeidl T(2020)Orderings of Data - More Than a Tripping HazardProceedings of the 32nd International Conference on Scientific and Statistical Database Management10.1145/3400903.3400911(1-4)Online publication date: 7-Jul-2020
Kłopotek MKłopotek R(2020)In-The-Limit Clustering AxiomsArtificial Intelligence and Soft Computing10.1007/978-3-030-61534-5_18(199-209)Online publication date: 12-Oct-2020
Kłopotek RKłopotek M(2019)On Probabilistic k-Richness of the k-Means AlgorithmsMachine Learning, Optimization, and Data Science10.1007/978-3-030-37599-7_22(259-271)Online publication date: 10-Sep-2019
Rubinstein A(2019)Hardness of Approximation Between P and NPundefinedOnline publication date: 30-May-2019
Cohen-Addad VKanade VMallmann-Trenn F(2018)Clustering redemption–beyond the impossibility of kleinberg's axiomsProceedings of the 32nd International Conference on Neural Information Processing Systems10.5555/3327757.3327943(8526-8535)Online publication date: 3-Dec-2018
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents