Journal
IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING
Volume 35, Issue 11, Pages 11259-11273Publisher
IEEE COMPUTER SOC
DOI: 10.1109/TKDE.2022.3233788
Keywords
Densest subgraph; periodic subgraph; temporal graph
Ask authors/readers for more resources
This paper proposes a novel model for finding the densest periodic subgraph in temporal graphs. By developing pruning techniques and efficient algorithms, efficient computation of periodic subgraphs is achieved.
Densest subgraphs are often interpreted as communities, based on a basic assumption that the connections inside a community are much denser than those between communities. In a graph with temporal information, a densest periodic subgraph is the most densely connected periodic behavior which needs to be captured. Unfortunately, the existing work do not model the densest periodic subgraph in temporal graphs, and the current algorithms for mining the densest subgraph cannot be applied to detect the densest periodic subgraph in the temporal networks. To tackle this problem, we propose a novel model, called the densest sigma-periodic subgraph, which presents the densest periodic subgraph whose period size is sigma. We prove that finding the densest sigma-periodic subgraph can be solved in polynomial time, but it is still challenging because the naive algorithm needs to repeatedly invoke a maximum flow algorithm for many periodic subgraphs. To compute the densest sigma-periodic subgraph efficiently, we first develop an effective pruning technique based on the degeneracy of the graph to significantly prune the number of the periodic subgraphs. Then, we present a more efficient algorithm that can reduce the computations for the degeneracy and maximum flow. Next, we develop a greedy algorithm that can compute the approximate densest sigma-periodic subgraph and achieve an approximation ratio of 1/2. Finally, the results of extensive experiments on several real-life datasets demonstrate the efficiency, scalability, and effectiveness of our algorithms.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available