Abstract
We say that there is a community structure in a graph when the nodes of the graph can be partitioned into groups (communities) such that each group is internally more densely connected than with the rest of the graph. However, the challenge seems to specify what is to be dense, and what is relatively more connected (there seems to exist a similar situation to what is a cluster in unsupervised learning). Recently,
Olsen [13] provided a general definition that is significantly more generic that others. We make two observations regarding such definition. First, we show that finding a community structure with k connected equal size communities is NP-complete. Then, we show that this problem can be solved efficiently on trees. Finally, we observed that every tree has a 2-community structure. This result is based on a reduction from an extremely popular heuristic (the GirvanNeumann algorithm [12]) for detecting communities in large networks.
Olsen [13] provided a general definition that is significantly more generic that others. We make two observations regarding such definition. First, we show that finding a community structure with k connected equal size communities is NP-complete. Then, we show that this problem can be solved efficiently on trees. Finally, we observed that every tree has a 2-community structure. This result is based on a reduction from an extremely popular heuristic (the GirvanNeumann algorithm [12]) for detecting communities in large networks.
Original language | English |
---|---|
Title of host publication | Proceedings of the Australasian Computer Science Week Multiconference |
Place of Publication | United States of America |
Publisher | Association for Computing Machinery (ACM) |
Pages | - |
Number of pages | 6 |
Volume | 01-05-February-2016 |
ISBN (Print) | 978-1-4503-4042-7 |
DOIs | |
Publication status | Published - 2016 |
Externally published | Yes |
Event | Australasian Computer Science Week (ACSW2016) - Canberra, Australia Duration: 2 Feb 2016 → 5 Feb 2016 https://cs.anu.edu.au/conf/acsw2016/ |
Conference
Conference | Australasian Computer Science Week (ACSW2016) |
---|---|
Abbreviated title | ACSW |
Country/Territory | Australia |
City | Canberra |
Period | 2/02/16 → 5/02/16 |
Internet address |