Computing Betweenness Centrality in Link Streams
Betweeness centrality is one of the most important concepts in graph analysis. It was recently extended to link streams, a graph generalization where links arrive over time. However, its computation raises non-trivial issues, due in particular to the fact that time is considered as continuous. We provide here the first algorithms to compute this generalized betweenness centrality, as well as several companion algorithms that have their own interest. They work in polynomial time and space, we illustrate them on typical examples, and we provide an implementation.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
ABCDE: Approximating Betweenness-Centrality ranking with progressive-DropEdge
Betweenness-centrality is a popular measure in network analysis that aims to describe the importance of nodes in a graph. It accounts for the fraction of shortest paths passing through that node and is a key measure in m…
Approximating Betweenness-Centrality rankingCommunity DetectionONBRA: Rigorous Estimation of the Temporal Betweenness Centrality in Temporal Networks
In network analysis, the betweenness centrality of a node informally captures the fraction of shortest paths visiting that node. The computation of the betweenness centrality measure is a fundamental task in the analysis…
Degree-Mass Message Passing for Betweenness Ranking in Directed and Undirected Networks
Computing the importance of nodes in networks is a long-standing fundamental problem that has driven extensive study of various centrality measures. A particularly well-known centrality measure is betweenness centrality,…
Graph Neural NetworkA stochastic block model for community detection in attributed networks
Community detection is an important content in complex network analysis. The existing community detection methods in attributed networks mostly focus on only using network structure, while the methods of integrating node…
ClusteringCommunity DetectionStochastic Block ModelDifferentially-Private Two-Party Egocentric Betweenness Centrality
We describe a novel protocol for computing the egocentric betweenness centrality of a node when relevant edge information is spread between two mutually distrusting parties such as two telecommunications providers. While…
Vocal Bursts Valence Prediction