Abstract
Community detection is a fundamental technique used to group similar nodes in information networks, which represent dependencies between individuals across various fields. However, current community detection methods leave much to be desired. In addition to the inherent limitations of some methods due to their objective functions, the optimization required by many community detection methods is NP-hard, necessitating heuristic algorithms. Consequently, the communities obtained are merely approximate solutions and do not precisely meet predefined community requirements. Furthermore, existing work often oversimplifies information networks by modeling them as graphs, thus neglecting higher-order dependency structures. Therefore, we propose the development of an analytical framework for community detection that is general, computable, and interpretable.Our framework introduces a concept of strength for finding maximal strong communities, enabling us to detect more densest k-subgraphs in polynomial time compared to existing methods. In particular, many existing works are confined to finding the maximal densest k-subgraphs. There are also compact dense subgraphs that are not the densest k-subgraphs, and our framework for finding maximal strong communities can detect them. Unlike existing methods that define locally densest subgraphs without natural extensions to weighted graphs, our framework is applicable to weighted/unweighted, directed/undirected graphs/hypergraphs. It also applies to a general notion of the density of information well beyond weighted graphs.
| Date of Award | 2 Sept 2024 |
|---|---|
| Original language | English |
| Awarding Institution |
|
| Supervisor | Chung CHAN (Supervisor) |