Ghent University Academic Bibliography

Advanced

Incompatibility boundaries for properties of community partitions

Arnaud Browet, Julien M Hendrickx and Alain Sarlette UGent (2018) IEEE TRANSACTIONS ON NETWORK SCIENCE AND ENGINEERING. 5(1). p.32-41
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.
Please use this url to cite or link to this publication:
author
organization
year
type
journalArticle (original)
publication status
published
subject
keyword
Network theory (graphs), partitioning algorithms, network topology, clustering algorithms
journal title
IEEE TRANSACTIONS ON NETWORK SCIENCE AND ENGINEERING
IEEE Trans. Netw. Sci. Eng.
volume
5
issue
1
pages
32 - 41
Web of Science id
000426717000004
ISSN
2327-4697
DOI
10.1109/TNSE.2017.2671905
language
English
UGent publication?
yes
classification
A2
copyright statement
I have transferred the copyright for this publication to the publisher
id
8556924
handle
http://hdl.handle.net/1854/LU-8556924
date created
2018-03-22 08:39:04
date last changed
2018-03-27 07:44:27
@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},
}

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.