|
Title:
|
FINDING COMMUNITIES BY CLUSTERING A GRAPH INTO OVERLAPPING SUBGRAPHS* |
|
Author(s):
|
Jeffrey Baumes , Mark Goldberg , Mukkai Krishnamoorthy , Malik Magdon-ismail , Nathan Preston |
|
ISBN:
|
972-99353-6-X |
|
Editors:
|
Nuno Guimarães and Pedro Isaías |
|
Year:
|
2005 |
|
Edition:
|
1 |
|
Keywords:
|
algorithms, communities, clustering, testing . |
|
Type:
|
Full Paper |
|
First Page:
|
97 |
|
Last Page:
|
104 |
|
Language:
|
English |
|
Cover:
|
|
|
Full Contents:
|
click to dowload 
|
|
Paper Abstract:
|
We present a new approach to the problem of finding communities: a community is a subset of actors who induce a locally optimal subgraph with respect to a density function defined on subsets of actors. Two different subsets with significant overlap can both be locally optimal, and in this way we may obtain overlapping communities. We design, implement, and test two novel efficient algorithms, RaRe and IS, which find communities according to our definition. These algorithms are shown to work effectively on both synthetic and real-world graphs, and also are shown to outperform a well-known k-neighborhood heuristic. |
|
|
|
|
|
|
