This Issue


International Journal of Bifurcation and Chaos: Vol. 17, No. 07
Print ISSN: 0218-1274
Online ISSN: 1793-6551

 
2016 Impact Factor
1.329
writing-guides   ealerts
Connect with WS
 

International Journal of Bifurcation and Chaos

in Applied Sciences and Engineering




CENTRALITY ESTIMATION IN LARGE NETWORKS

Research supported in part by DFG under grant Br 2158/2-3.

ULRIK BRANDES

Department of Computer and Information Science, University of Konstanz, 78457 Konstanz, Germany

CHRISTIAN PICH

Department of Computer and Information Science, University of Konstanz, 78457 Konstanz, Germany

Received: March 31, 2006
Revised: August 18, 2006

Centrality indices are an essential concept in network analysis. For those based on shortest-path distances the computation is at least quadratic in the number of nodes, since it usually involves solving the single-source shortest-paths (SSSP) problem from every node. Therefore, exact computation is infeasible for many large networks of interest today. Centrality scores can be estimated, however, from a limited number of SSSP computations. We present results from an experimental study of the quality of such estimates under various selection strategies for the source vertices.

Keywords: Complex networks; betweenness centrality; approximate computation
Cited by (71):
, , , . (2017) Local Community Detection in Dynamic Graphs Using Personalized Centrality. Algorithms 10:3, 102. Online publication date: 1-Sep-2017. [Crossref]
, , . (2017) How has the family firm literature addressed its heterogeneity through classification systems? An integrated analysis. European Journal of Family Business. Online publication date: 1-Jul-2017. [Crossref]
, , , . (2017) Hyperbolic Embedding for Efficient Computation of Path Centralities and Adaptive Routing in Large-Scale Complex Commodity Networks. IEEE Transactions on Network Science and Engineering 4:3, 140-153. Online publication date: 1-Jul-2017. [Crossref]
, , , . (2017) Optimized P2P streaming for wireless distributed networks. Pervasive and Mobile Computing. Online publication date: 1-Jun-2017. [Crossref]
, , . (2017) Uncovering the Importance of Relationship Characteristics in Social Networks: Implications for Seeding Strategies. Journal of Marketing Research 54:2, 187-201. Online publication date: 1-Apr-2017. [Crossref]
, , , . (2017) Graph Manipulations for Fast Centrality Computation. ACM Transactions on Knowledge Discovery from Data 11:3, 1-25. Online publication date: 10-Mar-2017. [Crossref]
, , , , . (2017) Graph Ranking Guarantees for Numerical Approximations to Katz Centrality. Procedia Computer Science 108, 68-78. Online publication date: 1-Jan-2017. [Crossref]
, . (2017) Fast approximation of average shortest path length of directed BA networks. Physica A: Statistical Mechanics and its Applications 466, 243-248. Online publication date: 1-Jan-2017. [Crossref]
, , . (2016) A penalty box approach for approximation betweenness and closeness centrality algorithms. Social Network Analysis and Mining 6:1. Online publication date: 1-Dec-2016. [Crossref]
, . (2016) Centrality in the global network of corporate control. Social Network Analysis and Mining 6:1. Online publication date: 1-Dec-2016. [Crossref]
, , , . (2016) Backbone discovery in traffic networks. International Journal of Data Science and Analytics 1:3-4, 215-227. Online publication date: 1-Nov-2016. [Crossref]
, . (2016) Approximating Betweenness Centrality in Fully Dynamic Networks. Internet Mathematics 12:5, 281-314. Online publication date: 2-Sep-2016. [Crossref]
, , . (2016) Attack Vulnerability of Network Controllability. PLOS ONE 11:9, e0162289. Online publication date: 2-Sep-2016. [Crossref]
, , . (2016) Assessing the Influence of an Individual Event in Complex Fault Spreading Network Based on Dynamic Uncertain Causality Graph. IEEE Transactions on Neural Networks and Learning Systems 27:8, 1615-1630. Online publication date: 1-Aug-2016. [Crossref]
. (2016) Betweenness centrality based connectivity aware routing algorithm for prolonging network lifetime in wireless sensor networks. Wireless Networks 22:5, 1605-1624. Online publication date: 1-Jul-2016. [Crossref]
, , , , , , . (2016) Nearly Optimal Distributed Algorithm for Computing Betweenness Centrality. 2016 IEEE 36th International Conference on Distributed Computing Systems (ICDCS), 271-280. [Crossref]
, , . (2016) Optimized cooperative streaming in wireless mesh networks. 2016 IFIP Networking Conference (IFIP Networking) and Workshops, 350-358. [Crossref]
, . (2016) Pop-routing: Centrality-based tuning of control messages for faster route convergence. IEEE INFOCOM 2016 - The 35th Annual IEEE International Conference on Computer Communications, 1-9. [Crossref]
, . (2016) Fast approximation of betweenness centrality through sampling. Data Mining and Knowledge Discovery 30:2, 438-475. Online publication date: 1-Mar-2016. [Crossref]
, , , , , . (2016) Articulation points guided redundancy elimination for betweenness centrality. ACM SIGPLAN Notices 51:8, 1-13. Online publication date: 27-Feb-2016. [Crossref]
, . (2016) Identification of Pivotal Causes and Spreaders in the Time-Varying Fault Propagation Model to Improve the Decision Making under Abnormal Situation. Quality and Reliability Engineering International 32:1, 99-109. Online publication date: 1-Feb-2016. [Crossref]
, . 2016. Distributed and Parallel Algorithm for Computing Betweenness Centrality. Advances in Artificial Intelligence - IBERAMIA 2016, 285-296. [Crossref]
, , . (2016) Efficient algorithms for updating betweenness centrality in fully dynamic graphs. Information Sciences 326, 278-296. Online publication date: 1-Jan-2016. [Crossref]
, . 2016. Path-Based and Whole-Network Measures. Encyclopedia of Social Network Analysis and Mining, 1-16. [Crossref]
, , , , . (2015) Second-order centrality correlation in scale-free networks. International Journal of Modern Physics C 26:10. Online publication date: 1-Oct-2015. [Abstract | PDF (1354 KB) | PDF Plus (236 KB)]
, , , . (2015) Betweenness centrality in Delay Tolerant Networks: A survey. Ad Hoc Networks 33, 284-305. Online publication date: 1-Oct-2015. [Crossref]
, , , . (2015) A Faster Algorithm to Update Betweenness Centrality After Node Alteration. Internet Mathematics 11:4-5, 403-420. Online publication date: 3-Sep-2015. [Crossref]
, , . (2015) Scalable Online Betweenness Centrality in Evolving Graphs. IEEE Transactions on Knowledge and Data Engineering 27:9, 2494-2506. Online publication date: 1-Sep-2015. [Crossref]
, , , . (2015) Distributed Current Flow Betweenness Centrality. 2015 IEEE 9th International Conference on Self-Adaptive and Self-Organizing Systems, 71-80. [Crossref]
, . (2015) Gender Prediction in Random Chat Networks Using Topological Network Structures and Masked Content. 2015 IEEE International Conference on Information Reuse and Integration, 174-181. [Crossref]
, . (2015) A Clustered Approach for Fast Computation of Betweenness Centrality in Social Networks. 2015 IEEE International Congress on Big Data, 47-54. [Crossref]
, , . (2015) Outlier detection in network data using the Betweenness Centrality. SoutheastCon 2015, 1-5. [Crossref]
, , , , . (2015) Topology manipulations for speeding betweenness centrality computation. Journal of Complex Networks 3:1, 84-112. Online publication date: 1-Mar-2015. [Crossref]
, . (2015) Estimating Centrality Statistics for Complete and Sampled Networks: Some Approaches and Complications. 2015 48th Hawaii International Conference on System Sciences, 1686-1695. [Crossref]
, , , . (2015) Spanning Edge Centrality. Proceedings of the 24th International Conference on World Wide Web - WWW '15, 732-742. [Crossref]
, , . (2015) Heuristic Algorithm for Approximation Betweenness Centrality Using Graph Coarsening. Procedia Computer Science 66, 83-92. Online publication date: 1-Jan-2015. [Crossref]
, . 2015. Fully-Dynamic Approximation of Betweenness Centrality. Algorithms - ESA 2015, 155-166. [Crossref]
, , . 2014. Betweenness Centrality in Graphs. Quantitative Graph Theory, 233-257. [Crossref]
, . (2014) Scalable and High Performance Betweenness Centrality on the GPU. SC14: International Conference for High Performance Computing, Networking, Storage and Analysis, 572-583. [Crossref]
, , . (2014) Decision Fusion for Multimodal Biometrics Using Social Network Analysis. IEEE Transactions on Systems, Man, and Cybernetics: Systems 44:11, 1522-1533. Online publication date: 1-Nov-2014. [Crossref]
, , . (2014) Node centrality awareness via swarming effects. 2014 IEEE International Conference on Systems, Man, and Cybernetics (SMC), 19-24. [Crossref]
, , , . (2014) Efficient extraction of high centrality vertices in distributed graphs. 2014 IEEE High Performance Extreme Computing Conference (HPEC), 1-7. [Crossref]
, , , . (2014) Extensive Gene Remodeling in the Viral World: New Evidence for Nongradual Evolution in the Mobilome Network. Genome Biology and Evolution 6:9, 2195-2205. Online publication date: 1-Sep-2014. [Crossref]
, , . (2014) Heuristical top-k: fast estimation of centralities in complex networks. Information Processing Letters 114:8, 432-436. Online publication date: 1-Aug-2014. [Crossref]
, . (2014) Revisiting Edge and Node Parallelism for Dynamic GPU Graph Analytics. 2014 IEEE International Parallel & Distributed Processing Symposium Workshops, 1396-1406. [Crossref]
, , , , . (2013) Identifying high betweenness centrality nodes in large social networks. Social Network Analysis and Mining 3:4, 899-914. Online publication date: 1-Dec-2013. [Crossref]
, , . (2013) An Efficient Approach to Updating Closeness Centrality and Average Path Length in Dynamic Networks. 2013 IEEE 13th International Conference on Data Mining, 867-876. [Crossref]
, . (2013) X10-based distributed and parallel betweenness centrality and its application to social analytics. 20th Annual International Conference on High Performance Computing, 109-118. [Crossref]
, , . (2013) Document similarity detection using semantic social network analysis on RDF citation graph. 2013 IEEE 9th International Conference on Emerging Technologies (ICET), 1-6. [Crossref]
, , . (2013) Betweenness computation in the single graph representation of hypergraphs. Social Networks 35:4, 561-572. Online publication date: 1-Oct-2013. [Crossref]
, , . (2013) The (betweenness) centrality of critical nodes and network cores. 2013 9th International Wireless Communications and Mobile Computing Conference (IWCMC), 90-95. [Crossref]
. (2013) Sources of Franco-German corporate support for the euro: The effects of business network centrality and political connections. European Union Politics 14:1, 115-139. Online publication date: 1-Mar-2013. [Crossref]
, , , , . (2013) Out on the Land: Income, Subsistence Activities, and Food Sharing Networks in Nain, Labrador. Journal of Anthropology 2013, 1-11. Online publication date: 1-Jan-2013. [Crossref]
, , , , . (2012) Heuristics for Speeding Up Betweenness Centrality Computation. 2012 International Conference on Privacy, Security, Risk and Trust and 2012 International Confernece on Social Computing, 302-311. [Crossref]
, , , . (2012) Fast Exact Computation of betweenness Centrality in Social Networks. 2012 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, 450-456. [Crossref]
, , , . (2012) Range-limited centrality measures in complex networks. Physical Review E 85:6. Online publication date: 1-Jun-2012. [Crossref]
, , , . (2012) A novel measure of edge centrality in social networks. Knowledge-Based Systems 30, 136-150. Online publication date: 1-Jun-2012. [Crossref]
. (2012) Some results on approximate 1-median selection in metric spaces. Theoretical Computer Science 426-427, 1-12. Online publication date: 1-Apr-2012. [Crossref]
, , , . (2012) Answering pattern match queries in large graph databases via graph embedding. The VLDB Journal 21:1, 97-120. Online publication date: 1-Feb-2012. [Crossref]
, , . (2011) Betweenness Centrality Approximations for an Internet Deployed P2P Reputation System. 2011 IEEE International Symposium on Parallel and Distributed Processing Workshops and Phd Forum, 1627-1634. [Crossref]
, , . (2011) Network community-detection enhancement by proper weighting. Physical Review E 83:4. Online publication date: 1-Apr-2011. [Crossref]
, , , . (2011) Second order centrality: Distributed assessment of nodes criticity in complex networks. Computer Communications 34:5, 619-628. Online publication date: 1-Apr-2011. [Crossref]
, , , , . 2011. One Tag to Bind Them All: Measuring Term Abstractness in Social Metadata. The Semanic Web: Research and Applications, 360-374. [Crossref]
, , , . 2011. Efficient Computation of Time-Dependent Centralities in Air Transportation Networks. WALCOM: Algorithms and Computation, 77-88. [Crossref]
, , . (2010) Centrality-based routing for Wireless Sensor Networks. 2010 IFIP Wireless Days, 1-5. [Crossref]
, , . (2010) Efficient Extraction of High-Betweenness Vertices. 2010 International Conference on Advances in Social Networks Analysis and Mining, 286-290. [Crossref]
, , . (2010) A DEGREE-BASED STRATEGY FOR CONSTRAINED PINNING CONTROL OF COMPLEX NETWORKS. International Journal of Bifurcation and Chaos 20:05, 1533-1539. Online publication date: 1-May-2010. [Abstract | PDF (234 KB) | PDF Plus (310 KB)]
, , , . (2008) On the Visualization of Social and other Scale-Free Networks. IEEE Transactions on Visualization and Computer Graphics 14:6, 1285-1292. Online publication date: 1-Nov-2008. [Crossref]
. (2008) On variants of shortest-path betweenness centrality and their generic computation. Social Networks 30:2, 136-145. Online publication date: 1-May-2008. [Crossref]
, . (2008) Centrality Based Visualization of Small World Graphs. Computer Graphics Forum 27:3, 975-982. Online publication date: 1-May-2008. [Crossref]
. (2008) Decentralized Network Analysis: A Proposal. 2008 IEEE 17th Workshop on Enabling Technologies: Infrastructure for Collaborative Enterprises, 111-114. [Crossref]