The projection method: a unified formalism for community detection
We present the class of projection methods for community detection that generalizes many popular community detection methods. In this framework, we represent each clustering (partition) by a vector on a high-dimensional hypersphere. A community detection method is a projection method if it can be de...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Frontiers Media S.A.
2024-02-01
|
| Series: | Frontiers in Complex Systems |
| Subjects: | |
| Online Access: | https://www.frontiersin.org/articles/10.3389/fcpxs.2024.1331320/full |
| _version_ | 1797295145556639744 |
|---|---|
| author | Martijn Gösgens Remco van der Hofstad Nelly Litvak |
| author_facet | Martijn Gösgens Remco van der Hofstad Nelly Litvak |
| author_sort | Martijn Gösgens |
| collection | DOAJ |
| description | We present the class of projection methods for community detection that generalizes many popular community detection methods. In this framework, we represent each clustering (partition) by a vector on a high-dimensional hypersphere. A community detection method is a projection method if it can be described by the following two-step approach: 1) the graph is mapped to a query vector on the hypersphere; and 2) the query vector is projected on the set of clustering vectors. This last projection step is performed by minimizing the distance between the query vector and the clustering vector, over the set of clusterings. We prove that optimizing Markov stability, modularity, the likelihood of planted partition models and correlation clustering fit this framework. A consequence of this equivalence is that algorithms for each of these methods can be modified to perform the projection step in our framework. In addition, we show that these different methods suffer from the same granularity problem: they have parameters that control the granularity of the resulting clustering, but choosing these to obtain clusterings of the desired granularity is nontrivial. We provide a general heuristic to address this granularity problem, which can be applied to any projection method. Finally, we show how, given a generator of graphs with community structure, we can optimize a projection method for this generator in order to obtain a community detection method that performs well on this generator. |
| first_indexed | 2024-03-07T21:42:31Z |
| format | Article |
| id | doaj.art-675c67bcb3f241f984d0b92d9d8217c6 |
| institution | Directory Open Access Journal |
| issn | 2813-6187 |
| language | English |
| last_indexed | 2024-03-07T21:42:31Z |
| publishDate | 2024-02-01 |
| publisher | Frontiers Media S.A. |
| record_format | Article |
| series | Frontiers in Complex Systems |
| spelling | doaj.art-675c67bcb3f241f984d0b92d9d8217c62024-02-26T04:52:07ZengFrontiers Media S.A.Frontiers in Complex Systems2813-61872024-02-01210.3389/fcpxs.2024.13313201331320The projection method: a unified formalism for community detectionMartijn GösgensRemco van der HofstadNelly LitvakWe present the class of projection methods for community detection that generalizes many popular community detection methods. In this framework, we represent each clustering (partition) by a vector on a high-dimensional hypersphere. A community detection method is a projection method if it can be described by the following two-step approach: 1) the graph is mapped to a query vector on the hypersphere; and 2) the query vector is projected on the set of clustering vectors. This last projection step is performed by minimizing the distance between the query vector and the clustering vector, over the set of clusterings. We prove that optimizing Markov stability, modularity, the likelihood of planted partition models and correlation clustering fit this framework. A consequence of this equivalence is that algorithms for each of these methods can be modified to perform the projection step in our framework. In addition, we show that these different methods suffer from the same granularity problem: they have parameters that control the granularity of the resulting clustering, but choosing these to obtain clusterings of the desired granularity is nontrivial. We provide a general heuristic to address this granularity problem, which can be applied to any projection method. Finally, we show how, given a generator of graphs with community structure, we can optimize a projection method for this generator in order to obtain a community detection method that performs well on this generator.https://www.frontiersin.org/articles/10.3389/fcpxs.2024.1331320/fullcommunity detectionclusteringmodularityMarkov stabilityCorrelation clusteringgranularity |
| spellingShingle | Martijn Gösgens Remco van der Hofstad Nelly Litvak The projection method: a unified formalism for community detection Frontiers in Complex Systems community detection clustering modularity Markov stability Correlation clustering granularity |
| title | The projection method: a unified formalism for community detection |
| title_full | The projection method: a unified formalism for community detection |
| title_fullStr | The projection method: a unified formalism for community detection |
| title_full_unstemmed | The projection method: a unified formalism for community detection |
| title_short | The projection method: a unified formalism for community detection |
| title_sort | projection method a unified formalism for community detection |
| topic | community detection clustering modularity Markov stability Correlation clustering granularity |
| url | https://www.frontiersin.org/articles/10.3389/fcpxs.2024.1331320/full |
| work_keys_str_mv | AT martijngosgens theprojectionmethodaunifiedformalismforcommunitydetection AT remcovanderhofstad theprojectionmethodaunifiedformalismforcommunitydetection AT nellylitvak theprojectionmethodaunifiedformalismforcommunitydetection AT martijngosgens projectionmethodaunifiedformalismforcommunitydetection AT remcovanderhofstad projectionmethodaunifiedformalismforcommunitydetection AT nellylitvak projectionmethodaunifiedformalismforcommunitydetection |