DMCS: Density modularity based community search

J Kim, S Luo, G Cong, W Yu - … of the 2022 International Conference on …, 2022 - dl.acm.org
Proceedings of the 2022 International Conference on Management of Data, 2022dl.acm.org
Community Search, or finding a connected subgraph (known as a community) containing
the given query nodes in a social network, is a fundamental problem. Most of the existing
community search models only focus on the internal cohesiveness of a community.
However, a high-quality community often has high modularity, which means dense
connections inside communities and sparse connections to the nodes outside the
community. In this paper, we conduct a pioneer study on searching a community with high …
Community Search, or finding a connected subgraph (known as a community) containing the given query nodes in a social network, is a fundamental problem. Most of the existing community search models only focus on the internal cohesiveness of a community. However, a high-quality community often has high modularity, which means dense connections inside communities and sparse connections to the nodes outside the community. In this paper, we conduct a pioneer study on searching a community with high modularity. We point out that while modularity has been popularly used in community detection (without query nodes), it has not been adopted for community search, surprisingly, and its application in community search (related to query nodes) brings in new challenges. We address these challenges by designing a new graph modularity function named Density Modularity. To the best of our knowledge, this is the first work on the community search problem using graph modularity. The community search based on the density modularity, termed as DMCS, is to find a community in a social network that contains all the query nodes and has high density-modularity. We prove that the DMCS problem is NP-hard. To efficiently address DMCS, we present new algorithms that run in log-linear time to the graph size. We conduct extensive experimental studies in real-world and synthetic networks, which offer insights into the efficiency and effectiveness of our algorithms. In particular, our algorithm achieves up to 8.5 times higher accuracy in terms of NMI than baseline algorithms.
ACM Digital Library
以上显示的是最相近的搜索结果。 查看全部搜索结果