Bridgeness: A Local Index on Edge Significance in Maintaining Global Connectivity

Abstract

Edges in a network can be divided into two kinds according to their different roles: some enhance the locality like the ones inside a cluster while others contribute to the global connectivity like the ones connecting two clusters. A recent study by Onnela et al uncovered the weak ties effects in mobile communication. In this article, we provide complementary results on document networks, that is, the edges connecting less similar nodes in content are more significant in maintaining the global connectivity. We propose an index named bridgeness to quantify the edge significance in maintaining connectivity, which only depends on local information of network topology. We compare the bridgeness with content similarity and some other structural indices according to an edge percolation process. Experimental results on document networks show that the bridgeness outperforms content similarity in characterizing the edge significance. Furthermore, extensive numerical results on disparate networks indicate that the bridgeness is also better than some well-known indices on edge significance, including the Jaccard coefficient, degree product and betweenness centrality.

10 pages, 4 figures, 1 table

References in corpus (10)

• Structure and tie strengths in mobile communication networks
• Predicting Missing Links via Local Information
• Detect overlapping and hierarchical community structure in networks
• Link Prediction Based on Local Random Walk
• Emergence of communities in weighted networks
• How to make a fragile network robust and vice versa
• Covariance, correlation matrix and the multi-scale community structure of networks
• Biased Percolation on Scale-free Networks
• Triangular clustering in document networks
• Empirical study on clique-degree distribution of networks

Cited by in corpus (14)

• Vital nodes identification in complex networks
• Spectral methods for the detection of network community structure: a comparative analysis
• Centrality-based identification of important edges in complex networks
• Exploring the structural regularities in networks
• Cumulative Effect in Information Diffusion: A Comprehensive Empirical Study on Microblogging Network
• Detecting global bridges in networks
• Influence of Reciprocal links in Social Networks
• Tie Strength Distribution in Scientific Collaboration Networks
• Underestimated cost of targeted attacks on complex networks
• Bridges in Complex Networks
• Identifying significant edges via neighborhood information
• Variability of Contact Process in Complex Networks
• Representative Methods of Computational Socioeconomics
• Competition Between Homophily and Information Entropy Maximization in Social Networks