The Experts below are selected from a list of 11487 Experts worldwide ranked by ideXlab platform
Marc Barthelemy - One of the best experts on this subject based on the ideXlab platform.
-
From the Betweenness Centrality in street networks to structural invariants in random planar graphs
Nature Communications, 2018Co-Authors: Alec Kirkley, Marc Barthelemy, Hugo Barbosa, Gourab GhoshalAbstract:The Betweenness Centrality, a path-based global measure of flow, is a static predictor of congestion and load on networks. Here we demonstrate that its statistical distribution is invariant for planar networks, that are used to model many infrastructural and biological systems. Empirical analysis of street networks from 97 cities worldwide, along with simulations of random planar graph models, indicates the observed invariance to be a consequence of a bimodal regime consisting of an underlying tree structure for high Betweenness nodes, and a low Betweenness regime corresponding to loops providing local path alternatives. Furthermore, the high Betweenness nodes display a non-trivial spatial clustering with increasing spatial correlation as a function of the edge-density. Our results suggest that the spatial distribution of Betweenness is a more accurate discriminator than its statistics for comparing static congestion patterns and its evolution across cities as demonstrated by analyzing 200 years of street data for Paris.
-
from the Betweenness Centrality in street networks to structural invariants in random planar graphs
arXiv: Physics and Society, 2018Co-Authors: Alec Kirkley, Marc Barthelemy, Hugo Barbosa, Gourab GhoshalAbstract:We demonstrate that the distribution of Betweenness Centrality (BC), a global structural metric based on network flow, is an invariant quantity in most planar graphs. We confirm this invariance through an empirical analysis of street networks from 97 of the most populous cities worldwide, at scales significantly larger than previous studies. We also find that the BC distribution is robust to major alterations in the network, including significant changes to its topology and edge weight structure, indicating that the only relevant factors shaping the distribution are the number of nodes and edges as well as the constraint of planarity. Through simulations of random planar graph models and analytical calculations on Cayley trees, this invariance is demonstrated to be a consequence of a bimodal regime consisting of an underlying tree structure for high BC nodes, and a low BC regime arising from the presence of loops providing local path alternatives. Furthermore, the high BC nodes display a non-trivial spatial dependence, with increasing spatial correlation as a function of the number of edges, leading them to cluster around the barycenter at large densities. Our results suggest that the spatial distribution of the BC is a more accurate discriminator when comparing patterns across cities. Moreover, the BC being a static predictor of congestion in planar graphs, the observed invariance and spatial dependence has practical implications for infrastructural and biological networks. In particular, for the case of street networks, as long as planarity is conserved, bottlenecks continue to persist, and the effect of planned interventions to alleviate structural congestion will be limited primarily to load redistribution, a feature confirmed by analyzing 200 years of data for central Paris.
-
group Betweenness and co Betweenness inter related notions of coalition Centrality
Social Networks, 2009Co-Authors: Eric D. Kolaczyk, David B. Chua, Marc BarthelemyAbstract:Abstract Vertex Betweenness Centrality is a metric that seeks to quantify a sense of the importance of a vertex in a network in terms of its ‘control’ on the flow of information along geodesic paths throughout the network. Two natural ways to extend vertex Betweenness Centrality to sets of vertices are (i) in terms of geodesic paths that pass through at least one of the vertices in the set, and (ii) in terms of geodesic paths that pass through all vertices in the set. The former was introduced by Everett and Borgatti [Everett, M., Borgatti, S., 1999. The Centrality of groups and classes. Journal of Mathematical Sociology 23 (3), 181–201], and called group Betweenness Centrality. The latter, which we call co-Betweenness Centrality here, has not been considered formally in the literature until now, to the best of our knowledge. In this paper, we show that these two notions of Centrality are in fact intimately related and, furthermore, that this relationship may be exploited to obtain deeper insight into both. In particular, we provide an expansion for group Betweenness in terms of increasingly higher orders of co-Betweenness, in a manner analogous to the Taylor series expansion of a mathematical function in calculus. We then demonstrate the utility of this expansion by using it to construct analytic lower and upper bounds for group Betweenness that involve only simple combinations of (i) the Betweenness of individual vertices in the group, and (ii) the co-Betweenness of pairs of these vertices. Accordingly, we argue that the latter quantity, i.e., pairwise co-Betweenness, is itself a fundamental quantity of some independent interest, and we present a computationally efficient algorithm for its calculation, which extends the algorithm of Brandes [Brandes, U., 2001. A faster algorithm for Betweenness Centrality. Journal of Mathematical Sociology 25, 163] in a natural manner. Applications are provided throughout, using a handful of different communication networks, which serve to illustrate the way in which our mathematical contributions allow for insight to be gained into the interaction of network structure, coalitions, and information flow in social networks.
Henning Meyerhenke - One of the best experts on this subject based on the ideXlab platform.
-
fully dynamic approximation of Betweenness Centrality
arXiv: Data Structures and Algorithms, 2015Co-Authors: Elisabetta Bergamini, Henning MeyerhenkeAbstract:Betweenness is a well-known Centrality measure that ranks the nodes of a network according to their participation in shortest paths. Since an exact computation is prohibitive in large networks, several approximation algorithms have been proposed. Besides that, recent years have seen the publication of dynamic algorithms for efficient recomputation of Betweenness in evolving networks. In previous work we proposed the first semi-dynamic algorithms that recompute an approximation of Betweenness in connected graphs after batches of edge insertions. In this paper we propose the first fully-dynamic approximation algorithms (for weighted and unweighted undirected graphs that need not to be connected) with a provable guarantee on the maximum approximation error. The transfer to fully-dynamic and disconnected graphs implies additional algorithmic problems that could be of independent interest. In particular, we propose a new upper bound on the vertex diameter for weighted undirected graphs. For both weighted and unweighted graphs, we also propose the first fully-dynamic algorithms that keep track of such upper bound. In addition, we extend our former algorithm for semi-dynamic BFS to batches of both edge insertions and deletions. Using approximation, our algorithms are the first to make in-memory computation of Betweenness in fully-dynamic networks with millions of edges feasible. Our experiments show that they can achieve substantial speedups compared to recomputation, up to several orders of magnitude.
-
fully dynamic approximation of Betweenness Centrality
European Symposium on Algorithms, 2015Co-Authors: Elisabetta Bergamini, Henning MeyerhenkeAbstract:Betweenness is a well-known Centrality measure that ranks the nodes of a network according to their participation in shortest paths. Since an exact computation is prohibitive in large networks, several approximation algorithms have been proposed. Besides that, recent years have seen the publication of dynamic algorithms for efficient recomputation of Betweenness in evolving networks. In previous work we proposed the first semi-dynamic algorithms that recompute an approximation of Betweenness in connected graphs after batches of edge insertions.
-
approximating Betweenness Centrality in large evolving networks
Algorithm Engineering and Experimentation, 2015Co-Authors: Elisabetta Bergamini, Henning Meyerhenke, Christian L StaudtAbstract:Betweenness Centrality ranks the importance of nodes by their participation in all shortest paths of the network. Therefore computing exact Betweenness values is impractical in large networks. For static networks, approximation based on randomly sampled paths has been shown to be significantly faster in practice. However, for dynamic networks, no approximation algorithm for Betweenness Centrality is known that improves on static recomputation. We address this deficit by proposing two incremental approximation algorithms (for weighted and unweighted connected graphs) which provide a provable guarantee on the absolute approximation error. Processing batches of edge insertions, our algorithms yield significant speedups up to a factor of 104 compared to restarting the approximation. This is enabled by investing memory to store and efficiently update shortest paths. As a building block, we also propose an asymptotically faster algorithm for updating the SSSP problem in unweighted graphs. Our experimental study shows that our algorithms are the first to make in-memory computation of a Betweenness ranking practical for million-edge semi-dynamic networks. Moreover, our results show that the accuracy is even better than the theoretical guarantees in terms of absolute errors and the rank of nodes is well preserved, in particular for those with high Betweenness.
Loet Leydesdorff - One of the best experts on this subject based on the ideXlab platform.
-
Betweenness Centrality as a Driver of Preferential Attachment in the Evolution of Research Collaboration Networks
Journal of Informetrics, 2012Co-Authors: Alireza Abbasi, Liaquat Hossain, Loet LeydesdorffAbstract:We analyze whether preferential attachment in scientific coauthorship networks is different for authors with different forms of Centrality. Using a complete database for the scientific specialty of research about "steel structures," we show that Betweenness Centrality of an existing node is a significantly better predictor of preferential attachment by new entrants than degree or closeness Centrality. During the growth of a network, preferential attachment shifts from (local) degree Centrality to Betweenness Centrality as a global measure. An interpretation is that supervisors of PhD projects and postdocs broker between new entrants and the already existing network, and thus become focal to preferential attachment. Because of this mediation, scholarly networks can be expected to develop differently from networks which are predicated on preferential attachment to nodes with high degree Centrality
-
Betweenness Centrality as an indicator of the interdisciplinarity of scientific journals
arXiv: Physics and Society, 2009Co-Authors: Loet LeydesdorffAbstract:In addition to science citation indicators of journals like impact and immediacy, social network analysis provides a set of Centrality measures like degree, Betweenness, and closeness Centrality. These measures are first analyzed for the entire set of 7,379 journals included in the Journal Citation Reports of the Science Citation Index and the Social Sciences Citation Index 2004, and then also in relation to local citation environments which can be considered as proxies of specialties and disciplines. Betweenness Centrality is shown to be an indicator of the interdisciplinarity of journals, but only in local citation environments and after normalization because otherwise the influence of degree Centrality (size) overshadows the Betweenness-Centrality measure. The indicator is applied to a variety of citation environments, including policy-relevant ones like biotechnology and nanotechnology.
-
Betweenness Centrality as an indicator of the interdisciplinarity of scientific journals
Journal of the Association for Information Science and Technology, 2007Co-Authors: Loet LeydesdorffAbstract:In addition to science citation indicators of journals like impact and immediacy, social network analysis provides a set of Centrality measures like degree, Betweenness, and closeness Centrality. These measures are first analyzed for the entire set of 7,379 journals included in the Journal Citation Reports of the Science Citation Index and the Social Sciences Citation Index 2004 (Thomson ISI, Philadelphia, PA), and then also in relation to local citation environments that can be considered as proxies of specialties and disciplines. Betweenness Centrality is shown to be an indicator of the interdisciplinarity of journals, but only in local citation environments and after normalization; otherwise, the influence of degree Centrality (size) overshadows the Betweenness-Centrality measure. The indicator is applied to a variety of citation environments, including policy-relevant ones like biotechnology and nanotechnology. The values of the indicator remain sensitive to the delineations of the set because of the indicator's local character. Maps showing interdisciplinarity of journals in terms of Betweenness Centrality can be drawn using information about journal citation environments, which is available online.
Matteo Riondato - One of the best experts on this subject based on the ideXlab platform.
-
abra approximating Betweenness Centrality in static and dynamic graphs with rademacher averages
ACM Transactions on Knowledge Discovery From Data, 2018Co-Authors: Matteo Riondato, Eli UpfalAbstract:ABPA Ξ AΣ (ABRAXAS): Gnostic word of mystic meaning. We present ABRA, a suite of algorithms to compute and maintain probabilistically guaranteed high-quality approximations of the Betweenness Centrality of all nodes (or edges) on both static and fully dynamic graphs. Our algorithms use progressive random sampling and their analysis rely on Rademacher averages and pseudodimension, fundamental concepts from statistical learning theory. To our knowledge, ABRA is the first application of these concepts to the field of graph analysis. Our experimental results show that ABRA is much faster than exact methods, and vastly outperforms, in both runtime number of samples, and accuracy, state-of-the-art algorithms with the same quality guarantees.
-
abra approximating Betweenness Centrality in static and dynamic graphs with rademacher averages
Knowledge Discovery and Data Mining, 2016Co-Authors: Matteo Riondato, Eli UpfalAbstract:We present ABRA, a suite of algorithms to compute and maintain probabilistically-guaranteed, high-quality, approximations of the Betweenness Centrality of all nodes (or edges) on both static and fully dynamic graphs. Our algorithms use progressive random sampling and their analysis rely on Rademacher averages and pseudodimension, fundamental concepts from statistical learning theory. To our knowledge, this is the first application of these concepts to the field of graph analysis. Our experimental results show that ABRA is much faster than exact methods, and vastly outperforms, in both runtime and number of samples, state-of-the-art algorithms with the same quality guarantees.
-
fast approximation of Betweenness Centrality through sampling
Data Mining and Knowledge Discovery, 2016Co-Authors: Matteo Riondato, Evgenios M KornaropoulosAbstract:Betweenness Centrality is a fundamental measure in social network analysis, expressing the importance or influence of individual vertices (or edges) in a network in terms of the fraction of shortest paths that pass through them. Since exact computation in large networks is prohibitively expensive, we present two efficient randomized algorithms for Betweenness estimation. The algorithms are based on random sampling of shortest paths and offer probabilistic guarantees on the quality of the approximation. The first algorithm estimates the Betweenness of all vertices (or edges): all approximate values are within an additive factor $$\varepsilon \in (0,1)$$??(0,1) from the real values, with probability at least $$1-\delta $$1-?. The second algorithm focuses on the top-K vertices (or edges) with highest Betweenness and estimate their Betweenness value to within a multiplicative factor $$\varepsilon $$?, with probability at least $$1-\delta $$1-?. This is the first algorithm that can compute such approximation for the top-K vertices (or edges). By proving upper and lower bounds to the VC-dimension of a range set associated with the problem at hand, we can bound the sample size needed to achieve the desired approximations. We obtain sample sizes that are independent from the number of vertices in the network and only depend on a characteristic quantity that we call the vertex-diameter, that is the maximum number of vertices in a shortest path. In some cases, the sample size is completely independent from any quantitative property of the graph. An extensive experimental evaluation on real and artificial networks shows that our algorithms are significantly faster and much more scalable as the number of vertices grows than other algorithms with similar approximation guarantees.
-
abra approximating Betweenness Centrality in static and dynamic graphs with rademacher averages
arXiv: Data Structures and Algorithms, 2016Co-Authors: Matteo Riondato, Eli UpfalAbstract:We present ABRA, a suite of algorithms that compute and maintain probabilistically-guaranteed, high-quality, approximations of the Betweenness Centrality of all nodes (or edges) on both static and fully dynamic graphs. Our algorithms rely on random sampling and their analysis leverages on Rademacher averages and pseudodimension, fundamental concepts from statistical learning theory. To our knowledge, this is the first application of these concepts to the field of graph analysis. The results of our experimental evaluation show that our approach is much faster than exact methods, and vastly outperforms, in both speed and number of samples, current state-of-the-art algorithms with the same quality guarantees.
-
fast approximation of Betweenness Centrality through sampling
Web Search and Data Mining, 2014Co-Authors: Matteo Riondato, Evgenios M KornaropoulosAbstract:Betweenness Centrality is a fundamental measure in social network analysis, expressing the importance or influence of individual vertices in a network in terms of the fraction of shortest paths that pass through them. Exact computation in large networks is prohibitively expensive and fast approximation algorithms are required in these cases. We present two efficient randomized algorithms for Betweenness estimation. The algorithms are based on random sampling of shortest paths and offer probabilistic guarantees on the quality of the approximation. The first algorithm estimates the Betweenness of all vertices: all approximated values are within an additive factor ɛ from the real values, with probability at least 1-δ. The second algorithm focuses on the top-K vertices with highest Betweenness and approximate their Betweenness within a multiplicative factor ɛ, with probability at least $1-δ. This is the first algorithm that can compute such approximation for the top-K vertices. We use results from the VC-dimension theory to develop bounds to the sample size needed to achieve the desired approximations. By proving upper and lower bounds to the VC-dimension of a range set associated with the problem at hand, we obtain a sample size that is independent from the number of vertices in the network and only depends on a characteristic quantity that we call the vertex-diameter, that is the maximum number of vertices in a shortest path. In some cases, the sample size is completely independent from any property of the graph. The extensive experimental evaluation that we performed using real and artificial networks shows that our algorithms are significantly faster and much more scalable as the number of vertices in the network grows than previously presented algorithms with similar approximation guarantees.
Vijaya Ramachandran - One of the best experts on this subject based on the ideXlab platform.
-
Decremental All-Pairs ALL Shortest Paths and Betweenness Centrality
2020Co-Authors: ⋆ Meghana Nasre, Matteo Pontecorvi, Vijaya RamachandranAbstract:Abstract. We consider the all pairs all shortest paths (APASP) problem, which maintains the shortest path dag rooted at every vertex in a directed graph G = (V, E) with positive edge weights. For this problem we present a decremental algorithm (that supports the deletion of a vertex, or weight increases on edges incident to a vertex). Our algorithm runs in amortized O(ν * 2 · log n) time per update, where n = |V |, and ν * bounds the number of edges that lie on shortest paths through any given vertex. Our APASP algorithm can be used for the decremental computation of Betweenness Centrality (BC), a graph parameter that is widely used in the analysis of large complex networks. No nontrivial decremental algorithm for either problem was known prior to our work. Our method is a generalization of the decremental algorithm of Demetrescu and Italiano [3] for unique shortest paths, and for graphs with ν * = O(n), we match the bound i
-
a round efficient distributed Betweenness Centrality algorithm
ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, 2019Co-Authors: Loc Hoang, Keshav Pingali, Matteo Pontecorvi, Roshan Dathathri, Gurbinder Gill, Bozhi You, Vijaya RamachandranAbstract:We present Min-Rounds BC (MRBC), a distributed-memory algorithm in the CONGEST model that computes the Betweenness Centrality (BC) of every vertex in a directed unweighted n-node graph in O(n) rounds. Min-Rounds BC also computes all-pairs-shortest-paths (APSP) in such graphs. It improves the number of rounds by at least a constant factor over previous results for unweighted directed APSP and for unweighted BC, both directed and undirected. We implemented MRBC in D-Galois, a state-of-the-art distributed graph analytics system, incorporated additional optimizations enabled by the D-Galois model, and evaluated its performance on a production cluster with up to 256 hosts using power-law and road networks. Compared to the BC algorithm of Brandes, on average, MRBC reduces the number of rounds by 14.0× and the communication time by 2.8× for the graphs in our test suite. As a result, MRBC is 2.1× faster on average than Brandes BC for real-world web-crawls on 256 hosts.
-
Betweenness Centrality incremental and faster
Mathematical Foundations of Computer Science, 2014Co-Authors: Meghana Nasre, Matteo Pontecorvi, Vijaya RamachandranAbstract:We present an incremental algorithm that updates the Betweenness Centrality (BC) score of all vertices in a graph G when a new edge is added to G, or the weight of an existing edge is reduced. Our incremental algorithm runs in O(v * · n) time, where v * is bounded by m *, the number of edges that lie on a shortest path in G. We achieve the same bound for the more general incremental vertex update problem. Even for a single edge update, our incremental algorithm is the first algorithm that is provably faster on sparse graphs than recomputing with the well-known static Brandes algorithm. It is also likely to be much faster than Brandes on dense graphs since m * is often close to linear in n. Our incremental algorithm is very simple, and we give an efficient cache-oblivious implementation that incurs O(n · sort(v *)) cache misses, where sort is a well-known measure for caching efficiency.
-
Betweenness Centrality incremental and faster
arXiv: Data Structures and Algorithms, 2013Co-Authors: Meghana Nasre, Matteo Pontecorvi, Vijaya RamachandranAbstract:We consider the incremental computation of the Betweenness Centrality of all vertices in a large complex network modeled as a graph G = (V, E), directed or undirected, with positive real edge-weights. The current widely used algorithm to compute the Betweenness Centrality of all vertices in G is the Brandes algorithm that runs in O(mn + n^2 log n) time, where n = |V| and m = |E|. We present an incremental algorithm that updates the Betweenness Centrality score of all vertices in G when a new edge is added to G, or the weight of an existing edge is reduced. Our incremental algorithm runs in O(m' n + n^2) time, where m' is the size of a certain subset of E*, the set of edges in G that lie on a shortest path. We achieve the same bound for the more general incremental update of a vertex v, where the edge update can be performed on any subset of edges incident to v. Our incremental algorithm is the first algorithm that is asymptotically faster on sparse graphs than recomputing with the Brandes algorithm. Our algorithm is also likely to be much faster than the Brandes algorithm on dense graphs since m*, the size of E*, is often close to linear in n. Our incremental algorithm is very simple and the only data structures it uses are arrays, lists, and stack. We give an efficient cache-oblivious implementation that incurs O(scan(n^2) + n sort(m')) cache misses, where scan and sort are well-known measures for efficient caching. We also give a static algorithm for computing Betweenness Centrality of all vertices that runs in time O(m* n + n^2 log n), which is faster than the Brandes algorithm on any graph with n log n = o(m) and m* = o(m).