Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userBetweenness Centrality in Some Classes of Graphs
145
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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.
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 strain, 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 Maccari 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
For a given class $mathcal{C}$ of graphs and given integers $m leq n$, let $f_mathcal{C}(n,m)$ be the minimal number $k$ such that every $k$ independent $n$-sets in any graph belonging to $mathcal{C}$ have a (possibly partial) rainbow independent $m$-set. Motivated by known results on the finiteness and actual value of $f_mathcal{C}(n,m)$ when $mathcal{C}$ is the class of line graphs of graphs, we study this function for various other classes.
For positive integers $n$ and $e$, let $kappa(n,e)$ be the minimum crossing number (the standard planar crossing number) taken over all graphs with $n$ vertices and at least $e$ edges. Pach, Spencer and Toth [Discrete and Computational Geometry 24 623--644, (2000)] showed that $kappa(n,e) n^2/e^3$ tends to a positive constant (called midrange crossing constant) as $nto infty$ and $n ll e ll n^2$, proving a conjecture of ErdH{o}s and Guy. In this note, we extend their proof to show that the midrange crossing constant exists for graph classes that satisfy a certain set of graph properties. As a corollary, we show that the the midrange crossing constant exists for the family of bipartite graphs. All these results have their analogues for rectilinear crossing numbers.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
