اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدScalable Online Betweenness Centrality in Evolving Graphs
66
0
0.0
(
0
)
نشر من قبل
Nicolas Kourtellis Ph.D.
تاريخ النشر
2014
مجال البحث
الهندسة المعلوماتية
والبحث باللغة
English
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Betweenness centrality is a classic measure that quantifies the importance of a graph element (vertex or edge) according to the fraction of shortest paths passing through it. This measure is notoriously expensive to compute, and the best known algorithm runs in O(nm) time. The problems of efficiency and scalability are exacerbated in a dynamic setting, where the input is an evolving graph seen edge by edge, and the goal is to keep the betweenness centrality up to date. In this paper we propose the first truly scalable algorithm for online computation of betweenness centrality of both vertices and edges in an evolving graph where new edges are added and existing edges are removed. Our algorithm is carefully engineered with out-of-core techniques and tailored for modern parallel stream processing engines that run on clusters of shared-nothing commodity hardware. Hence, it is amenable to real-world deployment. We experiment on graphs that are two orders of magnitude larger than previous studies. Our method is able to keep the betweenness centrality measures up to date online, i.e., the time to update the measures is smaller than the inter-arrival time between two consecutive updates.
قيم البحث
اقرأ أيضاً
87 -
Sunil Kumar R (Research Scholar
, Department of Computer Applications
, n Cochin University of Science
2014
There are several centrality measures that have been introduced and studied for real world networks. They account for the different vertex characteristics that permit them to be ranked in order of importance in the network. Betweenness centrality is
a measure of the influence of a vertex over the flow of information between every pair of vertices under the assumption that information primarily flows over the shortest path between them. In this paper we present betweenness centrality of some important classes of graphs.
Dense granular systems subjected to an imposed shear stress undergo stick-slip dynamics with systematic patterns of dilation-compaction. During each stick phase, as the frictional strength builds up, the granular system dilates to accommodate shear s
train, developing stronger force networks. During each slip event, when the stored energy is released, particles experience large rearrangements and the granular network can significantly change. Here, we use numerical simulations of 3D, sheared frictional packings to show that the mean betweenness centrality -- a property of network of interparticle connections -- follows consistent patterns during the stick-slip dynamics, showing sharp spikes at each slip event. We identify the source of this behavior as arising from the connectivity and contact arrangements of granular network during dilation-compaction cycles, and find that a lower potential for connection between particles leads to an increase of mean betweenness centrality in the system. Furthermore, we show that at high confinements, few particles lose contact during slip events, leading to a smaller change in granular connectivity and betweenness centrality.
Betweenness centrality is a graph parameter that has been successfully applied to network analysis. In the context of computer networks, it was considered for various objectives, ranging from routing to service placement. However, as observed by Macc
ari et al. [INFOCOM 2018], research on betweenness centrality for improving protocols was hampered by the lack of a usable, fully distributed algorithm for computing this parameter. We resolve this issue by designing an efficient algorithm for computing betweenness centrality, which can be implemented by minimal modifications to any distance-vector routing protocol based on Bellman-Ford. The convergence time of our implementation is shown to be proportional to the diameter of the network
Network analysis defines a number of centrality measures to identify the most central nodes in a network. Fast computation of those measures is a major challenge in algorithmic network analysis. Aside from closeness and betweenness, Katz centrality i
s one of the established centrality measures. In this paper, we consider the problem of computing rankings for Katz centrality. In particular, we propose upper and lower bounds on the Katz score of a given node. While previous approaches relied on numerical approximation or heuristics to compute Katz centrality rankings, we construct an algorithm that iteratively improves those upper and lower bounds until a correct Katz ranking is obtained. We extend our algorithm to dynamic graphs while maintaining its correctness guarantees. Experiments demonstrate that our static graph algorithm outperforms both numerical approaches and heuristics with speedups between 1.5x and 3.5x, depending on the desired quality guarantees. Our dynamic graph algorithm improves upon the static algorithm for update batches of less than 10000 edges. We provide efficient parallel CPU and GPU implementations of our algorithms that enable near real-time Katz centrality computation for graphs with hundreds of millions of nodes in fractions of seconds.
In the present paper, we study the robustness of two-dimensional random lattices (Delaunay triangulations) under attacks based on betweenness centrality. Together with the standard definition of this centrality measure, we employ a range-limited appr
oximation known as $ell$-betweenness, where paths having more than $ell$ steps are ignored. For finite $ell$, the attacks produce continuous percolation transitions that belong to the universality class of random percolation. On the other hand, the attack under the full range betweenness induces a discontinuous transition that, in the thermodynamic limit, occurs after removing a sub-extensive amount of nodes. This behavior is recovered for $ell$-betweenness if the cutoff is allowed to scale with the linear length of the network faster than $ellsim L^{0.91}$. Our results suggest that betweenness centrality encodes information on network robustness at all scales, and thus cannot be approximated using finite-ranged calculations without losing attack efficiency.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
