IEEE Transactions on Parallel and Distributed Systems · 2018 · 53 citations · 28 references
ComputingComputer ScienceAlgorithmsParallel AlgorithmsParallel ComputingGraph AlgorithmsGraph AnalyticsGraph TheoryDynamic Graph AlgorithmsDynamic Graph AnalysisGraph MatchingParallel Graph AlgorithmsParallel Matching AlgorithmsScalable Graph AlgorithmsTemporal Networks
The core number of vertices is a basic index depicting cohesiveness of a graph, and has been widely used in large-scale graph analytics. In this paper, we study the update of core numbers of vertices in dynamic graphs with edge insertions/deletions, which is known as the core maintenance problem. Different from previous approaches that just focus on the case of single-edge insertion/deletion and sequentially handle the edges when multiple edges are inserted/deleted, we investigate the parallelism in the core maintenance procedure. Specifically, we show that if the inserted/deleted edges constitute a matching, the core number update with respect to each inserted/deleted edge can be handled in parallel. Based on this key observation, we propose parallel algorithms for core maintenance in both cases of edge insertions and deletions. Extensive experiments are conducted to evaluate the efficiency, stability, parallelism and scalability of our algorithms on different types of real-world, synthetic graphs and temporal networks. Comparing with former approaches, our algorithms can improve the core maintenance efficiency significantly.
28
Emergence of Scaling in Random Networks
Albert-Ĺaszló Barabási, Réka Albert · Science · 1999 · 36.4K citations · Full text
Introduction to Social Network Methods
Robert Hanneman · 2001 · 4K citations
Identification of influential spreaders in complex networks
Maksim Kitsak, Lazaros K. Gallos, Shlomo Havlin et al. · Nature Physics · 2010 · 3.2K citations · Full text
R-MAT: A Recursive Model for Graph Mining
Deepayan Chakrabarti, Yiping Zhan, Christos Faloutsos · 2004 · 1.3K citations · Full text