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
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
ATZ-Fachkongress

Chassis.tech plus 2024


4 Kongresse in einer Veranstaltung

Treffen Sie in München die Fachleute von Chassis, Lenkung, Bremsen sowie Reifen/Räder.
Erweiterte Suche
Anmelden
nach oben
Knowledge and Information Systems
Erschienen in: Knowledge and Information Systems 3/2015

01.12.2015 | Regular Paper

Estimating robustness in large social graphs

verfasst von: Fragkiskos D. Malliaros, Vasileios Megalooikonomou, Christos Faloutsos

Erschienen in: Knowledge and Information Systems | Ausgabe 3/2015

Einloggen

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

search-config
loading …

Abstract

Given a large social graph, what can we say about its robustness? Broadly speaking, the property of robustness is crucial in real graphs, since it is related to the structural behavior of graphs to retain their connectivity properties after losing a portion of their edges/nodes. Can we estimate a robustness index for a graph quickly? Additionally, if the graph evolves over time, how this property changes? In this work, we are trying to answer the above questions studying the expansion properties of large social graphs. First, we present a measure that characterizes the robustness properties of a graph and also serves as global measure of the community structure (or lack thereof). We show how to compute this measure efficiently by exploiting the special spectral properties of real-world networks. We apply our method on several diverse real networks with millions of nodes, and we observe interesting properties for both static and time-evolving social graphs. As an application example, we show how to spot outliers and anomalies in graphs over time. Finally, we examine how graph generating models that mimic several properties of real-world graphs and behave in terms of robustness dynamics.
Vorheriger Artikel Triangle minimization in large networks
Nächster Artikel Optimal WCDMA network planning by multiobjective evolutionary algorithm with problem-specific genetic operation

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
This property simply means that the \(\sinh (\cdot )\) function retains the signs of the eigenvalues.
 
3
Personal communication with Michael Ley and Florian Reitz from DBLP.
 
4
The bipartite graphs do not have odd length closed walks, and thus, the \(\mathrm{SC}\) is computed based on the even length closed walks. This happens replacing the \(\sinh (\cdot )\) function with the \(\cosh (\cdot )\) [15]. But then the \(\mathrm{SC}\) for the bipartite graphs cannot be efficiently approximated using similar ideas with the proposed \(\mathrm{NSC}_k\) (Sect. 4), because of the fact that the \(\cosh (\cdot )\) is an even function. However, our approach for bipartite graphs (Sect. 4, Proposition 4.1) overcomes this bottleneck and can be efficiently computed for large-scale graphs.
 
Literatur
1.
Akoglu L, McGlohon M, Faloutsos C (2010) OddBall: spotting anomalies in weighted graphs. In: PAKDD, pp 410–421
2.
Albert R, Jeong H, Barabasi A-L (1999) Diameter of the world wide web. Nature 401:130–131CrossRef
3.
Albert R, Jeong H, Barabasi A-L (2000) Error and attack tolerance of complex networks. Nature 406(6794):378–382CrossRef
4.
Anagnostopoulos A, Brova G, Terzi E (2011) Peer and authority pressure in information-propagation models. In: PKDD, pp 76–91
5.
Baeza-Yates RA, Ribeiro-Neto B (1999) Modern information retrieval. Addison-Wesley Longman, New York
6.
7.
8.
Callaway DS, Newman MEJ, Strogatz SH, Watts DJ (2000) Network robustness and fragility: percolation on random graphs. Phys Rev Lett 80(25):5468–5471CrossRef
9.
Chakrabarti D, Faloutsos C (2012) Graph mining: laws, tools, and case studies. Synthesis lectures on data mining and knowledge discovery. Morgan and Claypool, San Rafael
10.
Chandola V, Banerjee A, Kumar V (2009) Anomaly detection: a survey. ACM Comput Surv 41(3):1–58CrossRef
11.
Chung FRK (1997) Spectral graph theory. CBMS, regional conference series in mathematics, no. 92. AMS
12.
Cohen R, Havlin S (2010) Complex networks: structure, robustness and function. Cambridge University Press, CambridgeCrossRef
13.
14.
Erdös P, Renyí A (1960) On the evolution of random graphs. Publ Math Inst Hung Acad Sci 5:17–61MATH
15.
16.
Estrada E (2006) Spectral scaling and good expansion properties in complex networks. Europhys Lett 73(4):649–655MathSciNetCrossRef
17.
Estrada E (2006) Network robustness to targeted attacks. The interplay of expansibility and degree distribution. Eur Phys J B 52:563–574CrossRefMATH
18.
Faloutsos M, Faloutsos P, Faloutsos C (1999) On power–law relationships of the Internet topology. In: SIGCOMM, pp 251–262
19.
20.
Golub GH, Van Loan CF (1996) Matrix computations, 3rd edn. Johns Hopkins University Press, BaltimoreMATH
21.
22.
23.
Kumar R, Novak J, Tomkins A (2006) Structure and evolution of online social networks. In: KDD, pp 611–617
24.
Lefevre K, Terzi E (2010) GraSS: Graph structure summarization. In: SDM, pp 454–465
25.
Leskovec J, Lang K, Dasgupta A, Mahoney M (2009) Community structure in large networks: natural cluster sizes and the absence of large well-defined clusters. Internet Math 6(1):29–123MathSciNetCrossRefMATH
26.
Leskovec J, Chakrabarti D, Kleinberg J, Faloutsos C (2010) Kronecker graphs: an approach to modeling networks. J Mach Learn Res 11:985–1042MathSciNetMATH
27.
Leskovec J, Huttenlocher D, Kleinberg J (2010) Predicting positive and negative links in online social networks. In: WWW, pp 641–650
28.
Leskovec J, Kleinberg J, Faloutsos C (2005) Graphs over time: densification laws, shrinking diameters and possible explanations. In: KDD, pp 177–187
29.
Leskovec J, Kleinberg J, Faloutsos C (2007) Graph evolution: densification and shrinking diameters. ACM Trans Knowl Discov Data 1(1):1–41
30.
Maiya AS, Berger-Wolf TY (2010) Expansion and search in networks. In: CIKM, pp 239–248
31.
Malliaros FD, Megalooikonomou V, Faloutsos C (2012) Fast robustness estimation in large social graphs: communities and anomaly detection. In: SDM, pp 942–953
32.
Malliaros FD, Vazirgiannis Michalis (2013) Clustering and community detection in directed networks: a survey. Phys Rep 533(4):95–142MathSciNetCrossRef
33.
Maserrat H, Pei J (2010) Neighbor query friendly compression of social networks. In: KDD, pp 533–542
34.
Mathioudakis M, Bonchi F, Castillo C, Gionis A, Ukkonen A (2011) Sparsification of influence networks. In: KDD, pp 529–537
35.
McGlohon M, Akoglu L, Faloutsos C (2008) Weighted graphs and disconnected components: patterns and a generator. In: KDD, pp 524–532
36.
Mihail M, Papadimitriou C, Saberi A (2011) On certain connectivity properties of the Internet topology. In: FOCS, pp 28–35
37.
Mislove A, Marcon M, Gummadi KP, Druschel P, Bhattacharjee B (2007) Measurement and analysis of online social networks. In: IMC, pp 29–42
38.
39.
40.
Newman MEJ, Park J (2003) Why social networks are different from other types of networks. Phys Rev E 68:036122CrossRef
41.
Newman MEJ (2006) Finding community structure in networks using the eigenvector of matrices. Phys Rev E 74(3):036104MathSciNetCrossRef
42.
Newman MEJ (2006) Modularity and community structure in networks. PNAS 103(23):8577–8582CrossRef
43.
Page L, Brin S, Motwani R, Winograd T (1999) The PageRank citation ranking: bringing order to the web. Technical Report, Stanford InfoLab
44.
Richardson M, Agrawal R, Domingos P (2003) Trust management for the semantic web. In: ISWC, pp 351–368
45.
Sala A, Cao L, Wilson C, Zablit R, Zheng H, Zhao BY (2010) Measurement-calibrated graph models for social network experiments. In: WWW, pp 861–870
46.
Satuluri V, Parthasarathy S (2009) Scalable graph clustering using stochastic flows: applications to community. discovery. In: KDD, pp 737–746
47.
Seshadhri C, Pinar A, Kolda TG (2013) An in-depth analysis of stochastic Kronecker graphs. JACM 60(2):13:1–13:32MathSciNetCrossRef
48.
Toivonen H, Zhou F, Hartikainen A, Hinkka A (2011) Compression of weighted graphs. In: KDD, pp 965–973
49.
Tsourakakis CE (2008) Fast counting of triangles in large real networks without counting: algorithms and laws. In: ICDM, pp 608–617
50.
Tsourakakis CE (2011) Counting triangles in real-world networks using projections. Knowl Inf Syst 26:501–520CrossRef
51.
Viswanath B, Mislove A, Cha M, Gummadi KP (2009) On the evolution of user interaction in Facebook. In: WOSN, pp 37–42
52.
Watts DJ, Strogatz SH (1998) Collective dynamics of ‘small-world’ networks. Nature 393(684):440–442CrossRef
Metadaten
Titel
Estimating robustness in large social graphs
verfasst von
Fragkiskos D. Malliaros
Vasileios Megalooikonomou
Christos Faloutsos
Publikationsdatum
01.12.2015
Verlag
Springer London
Erschienen in
Knowledge and Information Systems / Ausgabe 3/2015
Print ISSN: 0219-1377
Elektronische ISSN: 0219-3116
DOI
https://doi.org/10.1007/s10115-014-0810-7

Weitere Artikel der Ausgabe 3/2015

Knowledge and Information Systems 3/2015 Zur Ausgabe

Regular Paper

Multiplicative distance: a method to alleviate distance instability for high-dimensional data

Regular Paper

Evaluating link prediction methods

Regular Paper

Optimal WCDMA network planning by multiobjective evolutionary algorithm with problem-specific genetic operation

Regular Paper

On the anonymizability of graphs

Regular Paper

The Mask of ZoRRo: preventing information leakage from documents

Survey Paper

A survey on data stream clustering and classification

Premium Partner

    Bildnachweise