Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Social Network Analysis and Mining
Erschienen in: Social Network Analysis and Mining 1/2018

01.12.2018 | Original Article

Estimating degree rank in complex networks

verfasst von: Akrati Saxena, Ralucca Gera, S. R. S. Iyengar

Erschienen in: Social Network Analysis and Mining | Ausgabe 1/2018

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Identifying top-ranked nodes can be performed using different centrality measures, based on their characteristics and influential power. The most basic of all the ranking techniques is based on nodes degree. While finding the degree of a node requires local information, ranking the node based on its degree requires global information, namely the degrees of all the nodes of the network. It is infeasible to collect the global information for some graphs such as (i) the ones emerging from big data, (ii) dynamic networks, and (iii) distributed networks in which the whole graph is not known. In this work, we propose methods to estimate the degree rank of a node, that are faster than the classical method of computing the centrality value of all nodes and then rank a node. The proposed methods are modeled based on the network characteristics and sampling techniques, thus not requiring the entire network. We show that approximately \(1\%\) node samples are adequate to find the rank of a node with high accuracy.
Vorheriger Artikel An investigation into the requirements of privacy in social networks and factors contributing to users’ concerns about violation of their privacy
Nächster Artikel Overlapping community detection with preference and locality information: a non-negative matrix factorization approach

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Anhänge
Nur mit Berechtigung zugänglich
Fußnoten
1
Here, discrete probability values are considered as continuous probability density function, as this introduces a very small error.
 
Literatur
Backstrom L, Leskovec J (2011) Supervised random walks: predicting and recommending links in social networks. In: Proceedings of the fourth ACM international conference on Web search and data mining, ACM, pp 635–644
Boldi P, Vigna S (2004) The WebGraph framework I: Compression techniques. In: Proc. of the Thirteenth International World Wide Web Conference (WWW 2004), ACM Press, Manhattan, USA, pp 595–601
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
Cem E, Sarac K (2015) Estimating the size and average degree of online social networks at the extreme. In: Communications (ICC), 2015 IEEE International Conference on, IEEE, pp 1268–1273
Cem E, Sarac K (2016a) Average degree estimation under ego-centric sampling design. In: Computer Communications Workshops (INFOCOM WKSHPS), 2016 IEEE Conference on, IEEE, pp 152–157
Cem E, Sarac K (2016b) Estimation of structural properties of online social networks at the extreme. Comput Netw 108:323–344CrossRef
Chen D, Lü L, Shang MS, Zhang YC, Zhou T (2012) Identifying influential nodes in complex networks. Physica Stat Mech Appl 391(4):1777–1787CrossRef
Chen L, Karbasi A, Crawford FW (2016) Estimating the size of a large network and its communities from a random sample. In: Advances in Neural Information Processing Systems, pp 3072–3080
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
Cooper C, Radzik T, Siantos Y (2012) A fast algorithm to find all high degree vertices in power law graphs. In: Proceedings of the 21st International Conference on World Wide Web, ACM, pp 1007–1016
Dasgupta A, Kumar R, Sarlos T (2014) On estimating the average degree. In: Proceedings of the 23rd international conference on World wide web, ACM, pp 795–806
Davis B, Gera R, Lazzaro G, Lim BY, Rye EC (2016) The marginal benefit of monitor placement on networks. In: Cherifi H, Gonçalves B, Menezes R, Sinatra R (eds) Complex networks VII, Springer, Cham, pp 93–104CrossRef
De Choudhury M, Sundaram H, John A, Seligmann DD (2009) Social synchrony: Predicting mimicry of user actions in online social media. In: Computational Science and Engineering, 2009. CSE’09. International Conference on, IEEE, vol 4, pp 151–158
Eden T, Ron D, Seshadhri C (2016) Sublinear time estimation of degree distribution moments: The arboricity connection. arXiv preprint arXiv:​160403661
Erdős P, Rényi A (1960) On the evolution of random graphs. Publ Math Inst Hungar Acad Sci 5:17–61MathSciNetMATH
Fire M, Tenenboim L, Lesser O, Puzis R, Rokach L, Elovici Y (2011) Link prediction in social networks using computationally efficient topological features. In: Privacy, security, risk and trust (PASSAT) and IEEE third international confernece on social computing (SocialCom), IEEE, pp 73–80
Fortunato S, Boguñá M, Flammini A, Menczer F (2006) Approximating pagerank from in-degree. In: Aiello W, Broder A, Janssen J, Milios E (eds) International workshop on algorithms and models for the web-graph. Springer, Berlin, Heidelberg, pp 59–71
Freeman LC (1977) A set of measures of centrality based on betweenness. Sociometry 40(1):35–41CrossRef
Ghoshal G, Barabási AL (2011) Ranking stability and super-stable nodes in complex networks. Nat Commun 2:394CrossRef
Gjoka M, Kurant M, Butts CT, Markopoulou A (2010) Walking in Facebook: A case study of unbiased sampling of OSNs. In: INFOCOM, 2010 Proceedings IEEE, IEEE, pp 1–9
Goodman LA (1961) Snowball sampling. Ann Math Stat 32(1):148–170MATH
Haralabopoulos G, Anagnostopoulos I (2014) Real time enhanced random sampling of online social networks. J Netw Comput Appl 41:126–134CrossRef
Hardiman SJ, Katzir L (2013) Estimating clustering coefficients and size of social networks via random walk. In: Proceedings of the 22nd international conference on World Wide Web, International World Wide Web Conferences Steering Committee, pp 539–550
Hogg T, Lerman K (2012) Social dynamics of digg. EPJ Data Sci 1(1):1–26CrossRef
Hou B, Yao Y, Liao D (2012) Identifying all-around nodes for spreading dynamics in complex networks. Phys A Stat Mech Appl 391(15):4012–4017CrossRef
Konstas I, Stathopoulos V, Jose JM (2009) On social networks and collaborative recommendation. In: Proceedings of the 32nd international ACM SIGIR conference on Research and development in information retrieval, ACM, pp 195–202
Leskovec J, Faloutsos C (2006) Sampling from large graphs. In: Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, ACM, pp 631–636
Leskovec J, Kleinberg J, Faloutsos C (2007) Graph evolution: densification and shrinking diameters. ACM Trans Knowl Discov Data (TKDD) 1(1):2CrossRef
Lovász L (1993) Random walks on graphs: A survey. Comb Paul erdos is eighty 2(1):1–46
Lu J, Li D (2012) Sampling online social networks by random walk. In: Proceedings of the First ACM International Workshop on Hot Topics on Interdisciplinary Social Networks Research, ACM, pp 33–40
Lucchese R, Varagnolo D (2015) Networks cardinality estimation using order statistics. In: American Control Conference (ACC), 2015, IEEE, pp 3810–3817
Marchetti-Spaccamela A (1988) On the estimate of the size of a directed graph. In: International Workshop on Graph-Theoretic Concepts in Computer Science, Springer, pp 317–326
McAuley JJ, Leskovec J (2012) Learning to discover social circles in ego networks. NIPS 2012:548–56
Metropolis N, Rosenbluth AW, Rosenbluth MN, Teller AH, Teller E (1953) Equation of state calculations by fast computing machines. J Chem Phys 21(6):1087–1092CrossRef
Moré JJ (1978) The levenberg-marquardt algorithm: implementation and theory. In: Watson GA (ed) Numerical analysis. Springer, Berlin, Heidelberg, pp 105–116CrossRef
Musco C, Su HH, Lynch N (2016) Ant-inspired density estimation via random walks. In: Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, ACM, pp 469–478
Nazi A, Zhou Z, Thirumuruganathan S, Zhang N, Das G (2015) Walk, not wait: faster sampling over online social networks. Proc VLDB Endow 8(6):678–689CrossRef
Ribeiro B, Towsley D (2010) Estimating and sampling graphs with multidimensional random walks. In: Proceedings of the 10th ACM SIGCOMM conference on Internet measurement, ACM, pp 390–403
Ribeiro B, Towsley D (2012) On the estimation accuracy of degree distributions from graph sampling. In: Decision and Control (CDC), 2012 IEEE 51st Annual Conference on, IEEE, pp 5240–5247
Ribeiro B, Wang P, Murai F, Towsley D (2012) Sampling directed graphs with random walks. In: INFOCOM, 2012 Proceedings IEEE, IEEE, pp 1692–1700
Rossi RA, Ahmed NK (2015) The network data repository with interactive graph analytics and visualization. In: Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, http://​networkrepositor​y.​com
Salganik MJ, Heckathorn DD (2004) Sampling and estimation in hidden populations using respondent-driven sampling. Sociol Methodol 34(1):193–240CrossRef
Saxena A, Gera R, Iyengar S (2017) Observe locally rank globally. In: Proceedings of the 2017 IEEE/ACM international conference on advances in social networks analysis and mining. 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
Traud AL, Mucha PJ, Porter MA (2012) Social structure of Facebook networks. Phys A 391(16):4165–4180CrossRef
Voudigari E, Salamanos N, Papageorgiou T, Yannakoudakis EJ (2016) Rank degree: An efficient algorithm for graph sampling. In: Advances in Social Networks Analysis and Mining (ASONAM), 2016 IEEE/ACM International Conference on, IEEE, pp 120–129
Yang J, Leskovec J (2015) Defining and evaluating network communities based on ground-truth. Knowl Inf Syst 42(1):181–213CrossRef
Ye S, Wu SF (2011) Estimating the size of online social networks. Int J Soc Comput Cyber Phys Syst 1(2):160–179CrossRef
Yu Y, Fan S (2015) Node importance measurement based on the degree and closeness centrality. J Inf Commput Sci 12(3):1281–1291CrossRef
Zhou Z, Zhang N, Gong Z, Das G (2016) Faster random walks by rewiring online social networks on-the-fly. ACM Trans Database Syst (TODS) 40(4):26MathSciNetCrossRef
Metadaten
Titel
Estimating degree rank in complex networks
verfasst von
Akrati Saxena
Ralucca Gera
S. R. S. Iyengar
Publikationsdatum
01.12.2018
Verlag
Springer Vienna
Erschienen in
Social Network Analysis and Mining / Ausgabe 1/2018
Print ISSN: 1869-5450
Elektronische ISSN: 1869-5469
DOI
https://doi.org/10.1007/s13278-018-0520-3

Weitere Artikel der Ausgabe 1/2018

Social Network Analysis and Mining 1/2018 Zur Ausgabe

Original Article

An efficient and effective hop-based approach for influence maximization in social networks

Original Article

Keyword extraction from micro-blogs using collective weight

Original Article

Link prediction for interdisciplinary collaboration via co-authorship network

Original Article

An efficient method for mining the maximal α-quasi-clique-community of a given node in complex networks

Case Report

User profiling of the Twitter Social Network during the impeachment of Brazilian President

Original Article

Learning from noisy label proportions for classifying online social data

Premium Partner

    Bildnachweise