Effective and Efficient Community Search for Complex Network Semantics Capture: From Coarse-Grain to Fine-Grain

Download PDF

Abstract

To analyze the massive social networks for providing personalized services, community search is widely studied to find the densely connected subgraph that can reflect the network properties for a given query. The existing community search methods adopt single community model to make structural constraints on communities, which can only describe single interaction mode. Since they fail to capture the semantics of the network with multiple interaction modes, they struggle to find the representative communities. To solve this issue, we design a novel community model called ( 𝜏, 𝜌 ) camp to flexibly capture complex network semantics in any level of granularity. We propose the unified support maximized community search problem to find the communities with the densest network semantics, which is proven a NP-hard problem. By constructing a hierarchical index structure, we propose an approximate community search algorithm with approximation ratio of 2 and linear time complexity of the query size. Extensive experiments are conducted on two public datasets and two crawled datasets. The experimental results prove the effectiveness and efficiency of our method.