Dataset Information

Hierarchical Decomposition for Betweenness Centrality Measure of Complex Networks.

ABSTRACT: Betweenness centrality is an indicator of a node's centrality in a network. It is equal to the number of shortest paths from all vertices to all others that pass through that node. Most of real-world large networks display a hierarchical community structure, and their betweenness computation possesses rather high complexity. Here we propose a new hierarchical decomposition approach to speed up the betweenness computation of complex networks. The advantage of this new method is its effective utilization of the local structural information from the hierarchical community. The presented method can significantly speed up the betweenness calculation. This improvement is much more evident in those networks with numerous homogeneous communities. Furthermore, the proposed method features a parallel structure, which is very suitable for parallel computation. Moreover, only a small amount of additional computation is required by our method, when small changes in the network structure are restricted to some local communities. The effectiveness of the proposed method is validated via the examples of two real-world power grids and one artificial network, which demonstrates that the performance of the proposed method is superior to that of the traditional method.

SUBMITTER: Li Y

PROVIDER: S-EPMC5397849 | biostudies-other | 2017 Apr

REPOSITORIES: biostudies-other

ACCESS DATA

Publications

Hierarchical Decomposition for Betweenness Centrality Measure of Complex Networks.

Li Yong Y Li Wenguo W Tan Yi Y Liu Fang F Cao Yijia Y Lee Kwang Y KY

Scientific reports 20170420

Betweenness centrality is an indicator of a node's centrality in a network. It is equal to the number of shortest paths from all vertices to all others that pass through that node. Most of real-world large networks display a hierarchical community structure, and their betweenness computation possesses rather high complexity. Here we propose a new hierarchical decomposition approach to speed up the betweenness computation of complex networks. The advantage of this new method is its effective util ...[more]

PMID: 28425442

Similar Datasets

Project description:Members of a society interact using a variety of social behaviors, giving rise to a multi-faceted and complex social life. For the study of animal behavior, quantifying this complexity is critical for understanding the impact of social life on animals' health and fitness. Multilayer network approaches, where each interaction type represents a different layer of the social network, have the potential to better capture this complexity than single layer approaches. Calculating individuals' centrality within a multilayer social network can reveal keystone individuals and more fully characterize social roles. However, existing measures of multilayer centrality do not account for differences in the dynamics and functionality across interaction layers. Here we validate a new method for quantifying multiplex centrality called consensus ranking by applying this method to multiple social groups of a well-studied nonhuman primate, the rhesus macaque. Consensus ranking can suitably handle the complexities of animal social life, such as networks with different properties (sparse vs. dense) and biological meanings (competitive vs. affiliative interactions). We examined whether individuals' attributes or socio-demographic factors (sex, age, dominance rank and certainty, matriline size, rearing history) were associated with multiplex centrality. Social networks were constructed for five interaction layers (i.e., aggression, status signaling, conflict policing, grooming and huddling) for seven social groups. Consensus ranks were calculated across these five layers and analyzed with respect to individual attributes and socio-demographic factors. Generalized linear mixed models showed that consensus ranking detected known social patterns in rhesus macaques, showing that multiplex centrality was greater in high-ranking males with high certainty of rank and females from the largest families. In addition, consensus ranks also showed that females from very small families and mother-reared (compared to nursery-reared) individuals were more central, showing that consideration of multiple social domains revealed individuals whose social centrality and importance might otherwise have been missed.

Dataset Information

Hierarchical Decomposition for Betweenness Centrality Measure of Complex Networks.

Publications

Hierarchical Decomposition for Betweenness Centrality Measure of Complex Networks.

Similar Datasets

OmicsDI is part of the ELIXIR infrastructure

Tweets