.png){kind=icon}
Return
Distributed Truss Computation in Dynamic Graphs
.png){kind=icon}
OA
AI
DOI：10.26599/TST.2022.9010019.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Large-scale graphs usually exhibit global sparsity with local cohesiveness, and mining the representative cohesive subgraphs is a fundamental problem in graph analysis. The k-truss is one of the most commonly studied cohesive subgraphs, in which each edge is formed in at least k - 2 triangles. A critical issue in mining a k-truss lies in the computation of the trussness of each edge, which is the maximum value of k that an edge can be in a k-truss. Existing works mostly focus on truss computation in static graphs by sequential models. However, the graphs are constantly changing dynamically in the real world. We study distributed truss computation in dynamic graphs in this paper. In particular, we compute the trussness of edges based on the local nature of the k-truss in a synchronized node-centric distributed model. Iteratively decomposing the trussness of edges by relying only on local topological information is possible with the proposed distributed decomposition algorithm. Moreover, the distributed maintenance algorithm only needs to update a small amount of dynamic information to complete the computation. Extensive experiments have been conducted to show the scalability and efficiency of the proposed algorithm.
Keywords:
distributed algorithm
dynamic graph
graph mining
cohesive subgraph
k-truss
Journal
T
IF:
3.5
Papers:
987
Citations:
2.5K
Organization
Cited Papers
ShareSaveShareSaveShareSaveShareSaveDNA Footprints: Using Parasites to Detect Elusive Animals, Proof of Principle in Hedgehogs.png)
Animals
OAAI
AnimalsIF0
OAAIShareSaveShareSave
View more