Advanced search
2 files | 751.00 KB

Incompatibility boundaries for properties of community partitions

Author
Organization
Abstract
We prove the incompatibility of certain desirable properties of community partition quality functions. Our results generalize the impossibility result of [Kleinberg 2003] by considering sets of weaker properties. In particular, we use an alternative notion to solve the central issue of the consistency property. (The latter means that modifying the graph in a way consistent with a partition should not have counterintuitive effects). Our results clearly show that community partition methods should not be expected to perfectly satisfy all ideally desired properties. We then proceed to show that this incompatibility no longer holds when slightly relaxed versions of the properties are considered, and we provide examples of simple quality functions satisfying these relaxed properties. An experimental study of these quality functions shows a behavior comparable to established methods in some situations, but more debatable results in others. This suggests that defining a notion of good partition in communities probably requires imposing additional properties.
Keywords
Network theory (graphs), partitioning algorithms, network topology, clustering algorithms

Downloads

  • (...).pdf
    • full text
    • |
    • UGent only
    • |
    • PDF
    • |
    • 458.77 KB
  • DS118 i.pdf
    • full text
    • |
    • open access
    • |
    • PDF
    • |
    • 292.23 KB

Citation

Please use this url to cite or link to this publication:

Chicago
Browet, Arnaud, Julien M Hendrickx, and Alain Sarlette. 2018. “Incompatibility Boundaries for Properties of Community Partitions.” Ieee Transactions on Network Science and Engineering 5 (1): 32–41.
APA
Browet, A., Hendrickx, J. M., & Sarlette, A. (2018). Incompatibility boundaries for properties of community partitions. IEEE TRANSACTIONS ON NETWORK SCIENCE AND ENGINEERING, 5(1), 32–41.
Vancouver
1.
Browet A, Hendrickx JM, Sarlette A. Incompatibility boundaries for properties of community partitions. IEEE TRANSACTIONS ON NETWORK SCIENCE AND ENGINEERING. 2018;5(1):32–41.
MLA
Browet, Arnaud, Julien M Hendrickx, and Alain Sarlette. “Incompatibility Boundaries for Properties of Community Partitions.” IEEE TRANSACTIONS ON NETWORK SCIENCE AND ENGINEERING 5.1 (2018): 32–41. Print.
@article{8556924,
  abstract     = {We prove the incompatibility of certain desirable properties of community partition quality functions. Our results generalize the impossibility result of [Kleinberg 2003] by considering sets of weaker properties. In particular, we use an alternative notion to solve the central issue of the consistency property. (The latter means that modifying the graph in a way consistent with a partition should not have counterintuitive effects). Our results clearly show that community partition methods should not be expected to perfectly satisfy all ideally desired properties. We then proceed to show that this incompatibility no longer holds when slightly relaxed versions of the properties are considered, and we provide examples of simple quality functions satisfying these relaxed properties. An experimental study of these quality functions shows a behavior comparable to established methods in some situations, but more debatable results in others. This suggests that defining a notion of good partition in communities probably requires imposing additional properties.},
  author       = {Browet, Arnaud and Hendrickx, Julien M and Sarlette, Alain},
  issn         = {2327-4697},
  journal      = {IEEE TRANSACTIONS ON NETWORK SCIENCE AND ENGINEERING},
  keyword      = {Network theory (graphs),partitioning algorithms,network topology,clustering algorithms},
  language     = {eng},
  number       = {1},
  pages        = {32--41},
  title        = {Incompatibility boundaries for properties of community partitions},
  url          = {http://dx.doi.org/10.1109/TNSE.2017.2671905},
  volume       = {5},
  year         = {2018},
}

Altmetric
View in Altmetric
Web of Science
Times cited: