Top

Social Network Analysis and Mining

Published in:

01-12-2019 | Original Article

A heuristic approach to estimate nodes’ closeness rank using the properties of real world networks

Authors: Akrati Saxena, Ralucca Gera, S. R. S. Iyengar

Published in: Social Network Analysis and Mining | Issue 1/2019

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Centrality measures capture the intuitive notion of the importance of a node in a network. Importance of a node can be a very subjective term and is defined based on the context and the application. Closeness centrality is one of the most popular centrality measures which quantifies how close a node is to every other node in the network. It considers the average distance of a given node to all the other nodes in a network and requires one to know the complete information of the network. To compute the closeness rank of a node, we first need to compute the closeness value of all the nodes, and then compare them to get the rank of the node. In this work, we address the problem of estimating the closeness centrality rank of a node without computing the closeness centrality values of all the nodes in the network. We provide linear time heuristic algorithms which run in O(m), versus the classical algorithm which runs in time \(O(m \cdot n)\), where m is the number of edges and n is the number of nodes in the network. The proposed methods are applied to real-world networks, and their accuracy is measured using absolute and weighted error functions.

previous article Modeling memetics using edge diversity

next article ParSoDA: high-level parallel programming for social data mining

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

(2016) Spanish book network dataset – KONECT. URL http://konect.uni-koblenz.de/networks/lasagne-spanishbook

Bader DA, Madduri K (2006) Parallel algorithms for evaluating centrality indices in real-world networks. In: Parallel rocessing, 2006. ICPP 2006. International Conference on, IEEE, pp 539–550

Barabási AL, Albert R (1999) Emergence of scaling in random networks. Science 286(5439):509–512MathSciNetMATHCrossRef

Barzinpour F, Ali-Ahmadi BH, Alizadeh S, Jalali Naini SG (2014) Clustering networks heterogeneous data in defining a comprehensive closeness centrality index. Math Probl Eng

Bergamini E, Borassi M, Crescenzi P, Marino A, Meyerhenke H (2016) Computing top-k closeness centrality faster in unweighted graphs. In: 2016 Proceedings of the eighteenth workshop on algorithm engineering and experiments (ALENEX). SIAM, pp 68–80

Bollacker KD, Lawrence S, Giles CL(1998) Citeseer: An autonomous web agent for automatic retrieval and identification of interesting publications. In: Proceedings of the second international conference on autonomous agents, ACM, pp 116–123

Brandes U, Pich C (2007) Centrality estimation in large networks. Int J Bifurcat Chaos 17(07):2303–2318MathSciNetMATHCrossRef

Brandes U, Borgatti SP, Freeman LC (2016) Maintaining the duality of closeness and betweenness centrality. Soc Netw 44:153–159CrossRef

Brin S, Page L (1998) The anatomy of a large-scale hypertextual web search engine In: Seventh international world-wide web conference (www 1998), april 14-18, 1998, brisbane, australia. Brisbane, Australia

Carbaugh J, Debnath J, Fletcher M, Gera R, Lee WC, Nelson R (2017) Extracting information based on partial or complete network data. In: International conference on communication, management and information technology

Chan SY, Leung IXY, Liò P (2009) Fast centrality approximation in modular networks. In: Proceedings of the 1st ACM international workshop on Complex networks meet information & knowledge management, ACM, pp 31–38

Chen D, Lü L, Shang MS, Zhang YC, Zhou T (2012) Identifying influential nodes in complex networks. Phys A Stat Mech Appl 391(4):1777–1787CrossRef

Cho E, Myers SA, Leskovec J (2011) Friendship and mobility: user movement in location-based social networks. In: Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining, ACM, pp 1082–1090

Cohen E, Delling D, Pajor T, Werneck R (2014) Computing classic closeness centrality, at scale. In: Proceedings of the second ACM conference on online social networks. ACM, pp 37–50

Cormen TH, Leiserson CE, Rivest RL, Stein C (2001) Introduction to algorithms, vol 6. MIT press, CambridgeMATH

Du Y, Gao C, Chen X, Hu Y, Sadiq R, Deng Y (2015) A new closeness centrality measure via effective distance in complex networks. Chaos: an Interdisciplinary. J. Nonlin. Sci. 25(3):033,112

Eppstein D, Wang J (2004) Fast approximation of centrality. J Graph Algorithms Appl 8:39–45MathSciNetMATHCrossRef

Freeman LC (1977) A set of measures of centrality based on betweenness. Sociometry 35–41

Freeman LC (1978) Centrality in social networks conceptual clarification. Soc Netw 1(3):215–239CrossRef

Hogg T, Lerman K (2012) Social dynamics of digg. EPJ Data Sci 1(1):1–26CrossRef

Jarukasemratana S, Murata T, Liu X (2014) Community detection algorithm based on centrality and node closeness in scale-free networks. Trans Jpn Soc Artif Intell 29(2):234–244CrossRef

Jeong H, Mason SP, Barabási AL, Oltvai ZN (2001) Lethality and centrality in protein networks. Nature 411(6833):41–42CrossRef

Joshi-Tope G, Gillespie M, Vastrik I, D’Eustachio P, Schmidt E, de Bono B, Jassal B, Gopinath G, Wu G, Matthews L (2005) Reactome: a knowledgebase of biological pathways. Nucl Acids Res 33(1):428–432

Kaiser M, Hilgetag CC (2006) Nonoptimal component placement, but short processing paths, due to long-distance projections in neural systems. PLoS Comput Biol 2(7):e95CrossRef

Kas M, Wachs M, Carley KM, Carley LR (2013) Incremental algorithm for updating betweenness centrality in dynamically growing networks. In: Proceedings of the 2013 IEEE/ACM international conference on advances in social networks analysis and mining, ACM, pp 33–40

Katz L (1953) A new status index derived from sociometric analysis. Psychometrika 18(1):39–43MATHCrossRef

Kendall MG (1945) The treatment of ties in ranking problems. Biometrika 33(3):239–251MathSciNetMATHCrossRef

Kim J, Ahn H, Park M, Kim S, Kim KP (2016) An estimated closeness centrality ranking algorithm and its performance analysis in Large-Scale workflow-supported social networks. KSII Trans Int Inf Syst 10(3):1454–1466

Klimt B, Yang Y (2004) The enron corpus: a new dataset for email classification research. In: Boulicaut JF, Esposito F, Giannotti F, Pedreschi D (eds) European conference on machine learning (ECML 2004). Springer, Berlin, Heidelberg, pp 217–226CrossRef

Ko K, Lee KJ, Park C (2008) Rethinking preferential attachment scheme: degree centrality versus closeness centrality. Connections 28(1):4–15

Lehmann KA, Kaufmann M (2003) Decentralized algorithms for evaluating centrality in complex networks

Leskovec J, Kleinberg J, Faloutsos C (2007) Graph evolution: densification and shrinking diameters. ACM Trans Knowl Discov Data 1(1):2CrossRef

Leskovec J, Huttenlocher D, Kleinberg J (2010) Signed networks in social media. In: Proceedings of the SIGCHI conference on human factors in computing systems, ACM, pp 1361–1370

Lu F, Osthoff C, Ramos D, Nardes R, et al (2015) Mdaccer: Modified distributed assessment of the closeness centrality ranking in complex networks for massively parallel environments. In: 2015 International symposium on computer architecture and high performance computing workshop (SBAC-PADW), IEEE, pp 43–48

McAuley JJ, Leskovec J (2012) Learning to discover social circles in ego networks. In: NIPS 2012:548–56

Moré JJ (1978) The levenberg-marquardt algorithm: implementation and theory. In: Watson GA (ed) Numerical analysis. Springer, Berlin, Heidelberg, pp 105–116CrossRef

Newman ME (2001) Scientific collaboration networks. ii. Shortest paths, weighted networks, and centrality. Phys Rev E 64(1):016,132MathSciNetCrossRef

Newman ME (2003) The structure and function of complex networks. SIAM Rev 45(2):167–256MathSciNetMATHCrossRef

Okamoto K, Chen W, Li XY (2008) Ranking of closeness centrality for large-scale social networks. In: Preparata FP, Wu X, Yin J (eds) International workshop on Frontiers in algorithmics. Springer, Berlin, Heidelberg, pp 186–195CrossRef

Olsen PW, Labouseur AG, Hwang JH (2014) Efficient top-k closeness centrality search. In: Data engineering (ICDE), 2014 IEEE 30th international conference on, IEEE, pp 196–207

Opsahl T (2011) Why anchorage is not (that) important: Binary ties and sample selection. online] https://www.toreopsahlcom/2011/08/12/why-anchorage-is-not-that-important-binary-tiesand-sample-selection (accessed Sept 2013)

Park S, Park M, Kim H, Kim H, Yoon W, Yoon TB, Kim KP (2013) A closeness centrality analysis algorithm for workflow-supported social networks. In: Advanced communication technology (ICACT), 2013 15th International conference on, IEEE, pp 158–161

Pfeffer J, Carley KM (2012) k-centralities: local approximations of global measures based on shortest paths. In: Proceedings of the 21st international conference companion on World Wide Web, ACM, pp 1043–1050

Rattigan MJ, Maier M, Jensen D (2006) Using structure indices for efficient approximation of network properties. In: Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, ACM, pp 357–366

Richardson M, Agrawal R, Domingos P(2003) Trust management for the semantic web. In: International semantic Web conference, Springer, pp 351–368

Rochat Y (2009) Closeness centrality extended to unconnected graphs: The harmonic centrality index. In: ASNA, EPFL-CONF-200525

Ruslan N, Sharif S (2015) Improved closeness centrality using arithmetic mean approach. In: innovation and analytics conference and exhibition(IACE 2015): Proceedings of the 2nd innovation and analytics conference & Exhibition, AIP Publishing, vol 1691, p 050022

Sabidussi G (1966) The centrality index of a graph. Psychometrika 31(4):581–603MathSciNetMATHCrossRef

Sariyuce AE, Kaya K, Saule E, Catalyurek UV (2013) Incremental algorithms for network management and analysis based on closeness centrality. arXiv preprint arXiv:13030422

Saxena A, Iyengar S (2017) Global rank estimation. arXiv preprint arXiv:171011341

Saxena A, Iyengar S (2018) Estimating shell-index in a graph with local information. arXiv preprint arXiv:180510391

Saxena A, Malik V, Iyengar S (2015a) Estimating the degree centrality ranking of a node. arXiv preprint arXiv:151105732

Saxena A, Malik V, Iyengar S (2015b) Rank me thou shalln’t compare me. arXiv preprint arXiv:151109050

Saxena A, Gera R, Iyengar S (2017a) Degree ranking using local information. arXiv preprint arXiv:170601205

Saxena A, Gera R, Iyengar S (2017b) Fast estimation of closeness centrality ranking. In: Proceedings of the 2017 IEEE/ACM international conference on advances in social networks analysis and mining 2017, ACM, pp 80–85

Saxena A, Gera R, Iyengar S (2017c) A faster method to estimate closeness centrality ranking. arXiv preprint arXiv:170602083

Saxena A, Gera R, Iyengar S (2017d) Observe locally rank globally. In: Proceedings of the 2017 IEEE/ACM international conference on advances in social networks analysis and mining 2017, ACM, pp 139–144

Shaw ME (1954) Some effects of unequal distribution of information upon group performance in various communication nets. J Abnorm Soc Psychol 49(4):547–553CrossRef

Sporns O, Honey CJ, Kötter R (2007) Identification and classification of hubs in brain networks. PloS One 2(10):e1049CrossRef

Stephenson K, Zelen M (1989) Rethinking centrality: methods and examples. Soc Netw 11(1):1–37MathSciNetCrossRef

Sudarshan Iyengar S, Veni Madhavan C, Zweig KA, Natarajan A (2012) Understanding human navigation using network analysis. Top Cogn Sci 4(1):121–134CrossRef

Tallberg C (2000) Comparing degree-based and closeness-based centrality measures. Univ, Department of Statistics

Szczepański P, Rahwan T, Michalak TP, Wooldridge M (2016) Closeness centrality for networks with overlapping community structure. In: Thirtieth AAAI conference on artificial intelligence

Ufimtsev V, Bhowmick S (2014) An extremely fast algorithm for identifying high closeness centrality vertices in large-scale networks. In: Proceedings of the fourth workshop on irregular applications: architectures and algorithms, IEEE Press, pp 53–56

Viswanath B, Mislove A, Cha M, Gummadi KP (2009) On the evolution of user interaction in facebook. In: Proceedings of the 2nd ACM workshop on Online social networks, ACM, pp 37–42

Wang W, Tang CY (2015) Distributed estimation of closeness centrality. In: Decision and Control (CDC), 2015 IEEE 54th annual conference on, IEEE, pp 4860–4865

Wehmuth K, Ziviani A (2012) Distributed assessment of the closeness centrality ranking in complex networks. In: Proceedings of the fourth annual workshop on simplifying complex networks for practitioners, ACM, pp 43–48

Yan E, Ding Y (2009) Applying centrality measures to impact analysis: a coauthorship network analysis. J Am Soc Inf Sci Technol 60(10):2107–2118CrossRef

Yang J, Leskovec J (2015) Defining and evaluating network communities based on ground-truth. Knowl Inf Syst 42(1):181–213CrossRef

Yen CC, Yeh MY, Chen MS (2013) An efficient approach to updating closeness centrality and average path length in dynamic networks. In: Data mining (ICDM), 2013 IEEE 13th international conference on, IEEE, pp 867–876

Zar JH (1972) Significance testing of the spearman rank correlation coefficient. J Am Stat Assoc 67(339):578–580MATHCrossRef

Zhang B, Liu R, Massey D, Zhang L (2005) Collecting the internet as-level topology. ACM SIGCOMM Comput Commun Rev 35(1):53–61CrossRef

Zhang J, Ma X, Liu W, Bai Y (2012) Inferring community members in social networks by closeness centrality examination. In: Web information systems and applications conference (WISA), 2012 Ninth, IEEE, pp 131–134

Title: A heuristic approach to estimate nodes’ closeness rank using the properties of real world networks
Authors: Akrati Saxena
Ralucca Gera
S. R. S. Iyengar
Publication date: 01-12-2019
Publisher: Springer Vienna
Published in: Social Network Analysis and Mining / Issue 1/2019
Print ISSN: 1869-5450
Electronic ISSN: 1869-5469
DOI: https://doi.org/10.1007/s13278-018-0545-7

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 1/2019

Complex networks are structurally distinguishable by domain

False information detection in online content and its role in decision making: a systematic literature review

Tracing temporal communities and event prediction in dynamic social networks

Forming a well-connected team of experts based on a social network graph: a novel weighting approach

Diversified top-k search with relaxed graph simulation

Deep learning approaches for Arabic sentiment analysis

Premium Partner