Community detection by graph Voronoi diagrams
Accurate and efficient community detection in networks is a key challenge for complex network theory and its applications. The problem is analogous to cluster analysis in data mining, a field rich in metric space-based methods. Common to these methods is a geometric, distance-based definition of clu...
| Main Authors: | , , , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IOP Publishing
2014-01-01
|
| Series: | New Journal of Physics |
| Subjects: | |
| Online Access: | https://doi.org/10.1088/1367-2630/16/6/063007 |
| _version_ | 1827874209176485888 |
|---|---|
| author | Dávid Deritei Zsolt I Lázár István Papp Ferenc Járai-Szabó Róbert Sumi Levente Varga Erzsébet Ravasz Regan Mária Ercsey-Ravasz |
| author_facet | Dávid Deritei Zsolt I Lázár István Papp Ferenc Járai-Szabó Róbert Sumi Levente Varga Erzsébet Ravasz Regan Mária Ercsey-Ravasz |
| author_sort | Dávid Deritei |
| collection | DOAJ |
| description | Accurate and efficient community detection in networks is a key challenge for complex network theory and its applications. The problem is analogous to cluster analysis in data mining, a field rich in metric space-based methods. Common to these methods is a geometric, distance-based definition of clusters or communities. Here we propose a new geometric approach to graph community detection based on graph Voronoi diagrams. Our method serves as proof of principle that the definition of appropriate distance metrics on graphs can bring a rich set of metric space-based clustering methods to network science. We employ a simple edge metric that reflects the intra- or inter-community character of edges, and a graph density-based rule to identify seed nodes of Voronoi cells. Our algorithm outperforms most network community detection methods applicable to large networks on benchmark as well as real-world networks. In addition to offering a computationally efficient alternative for community detection, our method opens new avenues for adapting a wide range of data mining algorithms to complex networks from the class of centroid- and density-based clustering methods. |
| first_indexed | 2024-03-12T16:48:59Z |
| format | Article |
| id | doaj.art-cb281a5b780146949f8c025f42f43582 |
| institution | Directory Open Access Journal |
| issn | 1367-2630 |
| language | English |
| last_indexed | 2024-03-12T16:48:59Z |
| publishDate | 2014-01-01 |
| publisher | IOP Publishing |
| record_format | Article |
| series | New Journal of Physics |
| spelling | doaj.art-cb281a5b780146949f8c025f42f435822023-08-08T11:27:50ZengIOP PublishingNew Journal of Physics1367-26302014-01-0116606300710.1088/1367-2630/16/6/063007Community detection by graph Voronoi diagramsDávid Deritei0Zsolt I Lázár1István Papp2Ferenc Járai-Szabó3Róbert Sumi4Levente Varga5Erzsébet Ravasz Regan6Mária Ercsey-Ravasz7Faculty of Physics, Babeş-Bolyai University , Str. M.Kogălniceanu 1, RO-400084 Cluj-Napoca, RomaniaFaculty of Physics, Babeş-Bolyai University , Str. M.Kogălniceanu 1, RO-400084 Cluj-Napoca, RomaniaFaculty of Physics, Babeş-Bolyai University , Str. M.Kogălniceanu 1, RO-400084 Cluj-Napoca, RomaniaFaculty of Physics, Babeş-Bolyai University , Str. M.Kogălniceanu 1, RO-400084 Cluj-Napoca, RomaniaFaculty of Physics, Babeş-Bolyai University , Str. M.Kogălniceanu 1, RO-400084 Cluj-Napoca, RomaniaFaculty of Physics, Babeş-Bolyai University , Str. M.Kogălniceanu 1, RO-400084 Cluj-Napoca, RomaniaCenter for Vascular Biology Research, Department of Medicine , Beth Israel Deaconess Medical Center, Harvard Medical School, Boston, MA, USAFaculty of Physics, Babeş-Bolyai University , Str. M.Kogălniceanu 1, RO-400084 Cluj-Napoca, RomaniaAccurate and efficient community detection in networks is a key challenge for complex network theory and its applications. The problem is analogous to cluster analysis in data mining, a field rich in metric space-based methods. Common to these methods is a geometric, distance-based definition of clusters or communities. Here we propose a new geometric approach to graph community detection based on graph Voronoi diagrams. Our method serves as proof of principle that the definition of appropriate distance metrics on graphs can bring a rich set of metric space-based clustering methods to network science. We employ a simple edge metric that reflects the intra- or inter-community character of edges, and a graph density-based rule to identify seed nodes of Voronoi cells. Our algorithm outperforms most network community detection methods applicable to large networks on benchmark as well as real-world networks. In addition to offering a computationally efficient alternative for community detection, our method opens new avenues for adapting a wide range of data mining algorithms to complex networks from the class of centroid- and density-based clustering methods.https://doi.org/10.1088/1367-2630/16/6/063007complex networkscommunity detectionVoronoi diagrams |
| spellingShingle | Dávid Deritei Zsolt I Lázár István Papp Ferenc Járai-Szabó Róbert Sumi Levente Varga Erzsébet Ravasz Regan Mária Ercsey-Ravasz Community detection by graph Voronoi diagrams New Journal of Physics complex networks community detection Voronoi diagrams |
| title | Community detection by graph Voronoi diagrams |
| title_full | Community detection by graph Voronoi diagrams |
| title_fullStr | Community detection by graph Voronoi diagrams |
| title_full_unstemmed | Community detection by graph Voronoi diagrams |
| title_short | Community detection by graph Voronoi diagrams |
| title_sort | community detection by graph voronoi diagrams |
| topic | complex networks community detection Voronoi diagrams |
| url | https://doi.org/10.1088/1367-2630/16/6/063007 |
| work_keys_str_mv | AT davidderitei communitydetectionbygraphvoronoidiagrams AT zsoltilazar communitydetectionbygraphvoronoidiagrams AT istvanpapp communitydetectionbygraphvoronoidiagrams AT ferencjaraiszabo communitydetectionbygraphvoronoidiagrams AT robertsumi communitydetectionbygraphvoronoidiagrams AT leventevarga communitydetectionbygraphvoronoidiagrams AT erzsebetravaszregan communitydetectionbygraphvoronoidiagrams AT mariaercseyravasz communitydetectionbygraphvoronoidiagrams |