HoSIM: Higher-order Structural Importance based method for multiple local community detection

Local community detection has recently attracted much research attention. Many methods have been proposed for the single local community detection that finds a community containing the given set of query nodes. However, nodes may belong to several communities in the network, and detecting all the communities for the query node set, termed multiple local community detection (MLCD), is more important as it could uncover more potential information. MLCD is also more challenging because when a query node belongs to multiple communities, it is always located in the complicated overlapping region and the marginal region of communities. Accordingly, detecting multiple communities for such nodes by applying seed expansion methods from the nodes is insufficient.This work addresses the MLCD based on higher-order structural importance (HoSI). First, to effectively estimate the influence of higher-order structures, we propose a new variant of random walk called Active Random Walk to measure the HoSI score between nodes. Then, we propose two new metrics to evaluate the HoSI score of a subgraph to a node and the HoSI score of a node, respectively. Based on the proposed metrics, we present a novel algorithm called HoSIM to detect multiple local communities for a query node. HoSIM enforces three-stage processing, namely subgraph sampling, core member identification, and local community detection. The key idea is to utilize HoSI to find and identify the core members of communities relevant to the query node and optimize the generated communities. Extensive experiments illustrate the effectiveness of HoSIM.(c) 2022 Elsevier B.V. All rights reserved.

Automated summary

This article introduces the importance of multiple local community detection and proposes an algorithm called HoSIM based on higher-order structural importance. HoSIM measures the importance score between nodes using Active Random Walk and evaluates the importance score of a subgraph to a node and the importance score of a node with two new metrics. Experiments demonstrate the effectiveness of HoSIM.