.png){kind=icon}
返回
Distributed Truss Computation in Dynamic Graphs
.png){kind=icon}
OA
AI
DOI：10.26599/TST.2022.9010019.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
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.
Keyword:
distributed algorithm
dynamic graph
graph mining
cohesive subgraph
k-truss
期刊
T
IF:
3.5
论文数:
987
被引数:
2.5K
机构
引用论文
分享收藏分享收藏DNA Footprints: Using Parasites to Detect Elusive Animals, Proof of Principle in Hedgehogs.png)
Animals
OAAI
AnimalsIF0
OAAI分享收藏分享收藏
查看更多内容