Game Theoretic Clustering for Finding Strong Communities
We address the challenge of identifying meaningful communities by proposing a model based on convex game theory and a measure of community strength. Many existing community detection methods fail to provide unique solutions, and it remains unclear how the solutions depend on initial conditions. Our...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2024-03-01
|
| Series: | Entropy |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1099-4300/26/3/268 |
| _version_ | 1797241173796978688 |
|---|---|
| author | Chao Zhao Ali Al-Bashabsheh Chung Chan |
| author_facet | Chao Zhao Ali Al-Bashabsheh Chung Chan |
| author_sort | Chao Zhao |
| collection | DOAJ |
| description | We address the challenge of identifying meaningful communities by proposing a model based on convex game theory and a measure of community strength. Many existing community detection methods fail to provide unique solutions, and it remains unclear how the solutions depend on initial conditions. Our approach identifies strong communities with a hierarchical structure, visualizable as a dendrogram, and computable in polynomial time using submodular function minimization. This framework extends beyond graphs to hypergraphs or even polymatroids. In the case when the model is graphical, a more efficient algorithm based on the max-flow min-cut algorithm can be devised. Though not achieving near-linear time complexity, the pursuit of practical algorithms is an intriguing avenue for future research. Our work serves as the foundation, offering an analytical framework that yields unique solutions with clear operational meaning for the communities identified. |
| first_indexed | 2024-04-24T18:19:07Z |
| format | Article |
| id | doaj.art-669099df1c704f80836988ff1c4592e1 |
| institution | Directory Open Access Journal |
| issn | 1099-4300 |
| language | English |
| last_indexed | 2024-04-24T18:19:07Z |
| publishDate | 2024-03-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Entropy |
| spelling | doaj.art-669099df1c704f80836988ff1c4592e12024-03-27T13:37:00ZengMDPI AGEntropy1099-43002024-03-0126326810.3390/e26030268Game Theoretic Clustering for Finding Strong CommunitiesChao Zhao0Ali Al-Bashabsheh1Chung Chan2Department of Computer Science, City University of Hong Kong, Hong Kong, ChinaSchool of General Engineering, Beihang University, Beijing 100191, ChinaDepartment of Computer Science, City University of Hong Kong, Hong Kong, ChinaWe address the challenge of identifying meaningful communities by proposing a model based on convex game theory and a measure of community strength. Many existing community detection methods fail to provide unique solutions, and it remains unclear how the solutions depend on initial conditions. Our approach identifies strong communities with a hierarchical structure, visualizable as a dendrogram, and computable in polynomial time using submodular function minimization. This framework extends beyond graphs to hypergraphs or even polymatroids. In the case when the model is graphical, a more efficient algorithm based on the max-flow min-cut algorithm can be devised. Though not achieving near-linear time complexity, the pursuit of practical algorithms is an intriguing avenue for future research. Our work serves as the foundation, offering an analytical framework that yields unique solutions with clear operational meaning for the communities identified.https://www.mdpi.com/1099-4300/26/3/268game theorycommunity detectionhierarchical clustering |
| spellingShingle | Chao Zhao Ali Al-Bashabsheh Chung Chan Game Theoretic Clustering for Finding Strong Communities Entropy game theory community detection hierarchical clustering |
| title | Game Theoretic Clustering for Finding Strong Communities |
| title_full | Game Theoretic Clustering for Finding Strong Communities |
| title_fullStr | Game Theoretic Clustering for Finding Strong Communities |
| title_full_unstemmed | Game Theoretic Clustering for Finding Strong Communities |
| title_short | Game Theoretic Clustering for Finding Strong Communities |
| title_sort | game theoretic clustering for finding strong communities |
| topic | game theory community detection hierarchical clustering |
| url | https://www.mdpi.com/1099-4300/26/3/268 |
| work_keys_str_mv | AT chaozhao gametheoreticclusteringforfindingstrongcommunities AT alialbashabsheh gametheoreticclusteringforfindingstrongcommunities AT chungchan gametheoreticclusteringforfindingstrongcommunities |