nach oben

Social Network Analysis and Mining

Erschienen in:

01.12.2016 | Original Article

Striations in PageRank-ordered matrices

verfasst von: Corey Pennycuff, Tim Weninger

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

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Patterns often appear in a variety of large, real-world networks, and interesting physical phenomena are often explained by network topology as in the case of the bow-tie structure of the World Wide Web, or the small-world phenomenon in social networks. The discovery and modeling of such regular patterns has a wide application from disease propagation to financial markets. In this work, we describe a newly discovered regularly occurring striation pattern found in the PageRank ordering of adjacency matrices that encode real-world networks. We demonstrate that these striations are the result of well-known graph-generation processes resulting in regularities that are manifested in the typical neighborhood distribution. The spectral view explored in this paper encodes a tremendous amount about the explicit and implicit topology of a given network, so we also discuss the interesting network properties, outliers and anomalies that a viewer can determine from a brief look at the re-ordered matrix.

Vorheriger Artikel Network topology and mean infection times

Nächster Artikel Structure and causality in the world system

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

Nur mit Berechtigung zugänglich

Abbassi Z, Mirrokni VS (2007) A recommender system based on local random walks and spectral methods. In: Proceedings of WebKDD and SNA-KDD, ACM, pp 102–108

Albert R, Jeong H, Barabási AL (1999) Internet: diameter of the World-Wide Web. Nature 401(6749):130–131CrossRef

Andersen R, Chung F, Lang K (2006) Local graph partitioning using PageRank vectors. In: FOCS, IEEE, pp 475–486 24

Barabasi AL, Albert R (1999) Emergence of scaling in random networks. Science 286(5439):509–512MathSciNetCrossRefMATH

Barabasi AL, Albert R, Jeong H (2000) Scale-free characteristics of random networks: the topology of the World-Wide Web. Phys A 281(1):69–77CrossRef

Barrat A, Weigt M (2000) On the properties of small-world network models. Eur Phys J B 13(3):547–560CrossRef

Becchetti L, Castillo C (2006) The distribution of PageRank follows a power-law only for particular values of the damping factor. In: WWW, ACM, pp 941–942

Bertin J (1973) S´emiologie graphique. Les diagrammes-les r´eseaux-les cartes

Blandford DK, Blelloch GE, Kash IA (2003) Compact representations of separable graphs. In: SODA, ACM/SIAM, pp 679–688

Chakrabarti D, Zhan Y, Blandford D, Faloutsos C, Blello G (2004a) Netmine: mining tools for large graphs. In: SDM workshop on link analysis, counterterrorism, and privacy, SIAM

Chakrabarti D, Zhan Y, Faloutsos C (2004b) R-mat: a recursive model for graph mining. In: SDM, SIAM, pp 442–446

Chakrabarti D, Faloutsos C, Zhan Y (2007) Visualization of large networks with min-cut plots, A-plots and R-MAT. Int J Hum-Comput Stud 65(5):434–445CrossRef

Cho E, Myers SA, Leskovec J (2011) Friendship and mobility: user movement in location-based social networks. In: SIGKDD, ACM, pp 1082–1090

Doreian P, Batagelj V, Ferligoj A (2005) Generalized blockmodeling, vol 25. Cambridge University Press, CambridgeMATH

Franceschet M (2011) PageRank: standing on the shoulders of giants. Commun ACM 54(6):92–101CrossRef

George JA (1971) Computer implementation of the finite element method. Technical Report, DTIC Document

George A, Liu J (1981) Computer solution of large sparse positive definite systems. Prentice-Hall, Englewood CliffsMATH

Ghoniem M, Fekete JD, Castagliola P (2005) On the readability of graphs using node-link and matrix-based representations: a controlled experiment and statistical analysis. Inf Vis 4(2):114–135CrossRef

Girvan M, Newman ME (2002) Community structure in social and biological networks. Proc Natl Acad Sci 99(12):7821–7826MathSciNetCrossRefMATH

Hagberg AA, Schult DA, Swart PJ (2008) Exploring network structure, dynamics, and function using NetworkX. In: SciPy, Pasadena, CA USA, pp 11–15

Kang U, Meeder B, Faloutsos C (2011) Spectral analysis for billion-scale graphs: discoveries and implementation. In: Advances in knowledge discovery and data mining. Springer, pp 13–25

King IP (1970) An automatic reordering scheme for simultaneous equations derived from network systems. Int J Numer Meth Eng 2(4):523–533CrossRef

Kleinberg JM (1999) Authoritative sources in a hyperlinked environment. J ACM 46(5):604–632MathSciNetCrossRefMATH

Knuth DE (1993) The Stanford GraphBase: a platform for combinatorial computing, vol 37. Addison-Wesley, ReadingMATH

Langville AN, Meyer CD (2005) A survey of eigenvector methods for web information retrieval. SIAM Rev 47(1):135–161MathSciNetCrossRefMATH

Lempel R, Moran S (2000) The stochastic approach for link-structure analysis (SALSA) and the TKC effect. Comput Netw 33(1):387–401CrossRef

Leskovec J, Kleinberg J, Faloutsos C (2005) Graphs over time: densification laws, shrinking diameters and possible explanations. In: SIGKDD, ACM, pp 177–187

Leskovec J, Adamic LA, Huberman BA (2007a) The dynamics of viral marketing. ACM Trans Web 1(1):5CrossRef

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

Leskovec J, Chakrabarti D, Kleinberg J, Faloutsos C, Ghahramani Z (2010) Kronecker graphs: an approach to modeling networks. J Mach Learn Res 11:985–1042MathSciNetMATH

Liben-Nowell D, Kleinberg J (2007) The link-prediction problem for social networks. J Am Soc Inf Sci Technol 58(7):1019–1031CrossRef

Lusseau D, Schneider K, Boisseau O, Haase P, Slooten E, Dawson S (2003) The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations. Behav Ecol Sociobiol 54(4):396–405CrossRef

McCormick WT Jr, Schweitzer PJ, White TW (1972) Problem decomposition and data reorganization by a clustering technique. Oper Res 20(5):993–1009CrossRefMATH

Mueller C, Martin B, Lumsdaine A (2007a) A Comparison of vertex ordering algorithms for large graph visualization. In: APVIS, IEEE, pp 141–148

Mueller C, Martin B, Lumsdaine A (2007b) Interpreting large visual similarity matrices. In: APVIS, IEEE, pp 149–152

Newman MEJ (2002) Assortative mixing in networks. Phys Rev Lett 89(208):701

Page L, Brin S, Motwani R, Winograd T (1999) The PageRank citation ranking: bringing order to the web, technical report, Stanford University, Stanford, CA

Pandurangan G, Raghavan P, Upfal E (2002) Using PageRank to characterize web structure. In: Computing and combinatorics. Springer, pp 330–339

Perra N, Fortunato S (2008) Spectral centrality measures in complex networks. Phys Rev E 78(036):107MathSciNet

Prakash BA, Sridharan A, Seshadri M, Machiraju S, Faloutsos C (2010) Eigenspokes: surprising patterns and scalable community chipping in large graphs. In: Advances in knowledge discovery and data mining. Springer, pp 435–448

Sloan S (1986) An algorithm for profile and wavefront reduction of sparse matrices. Int J Numer Meth Eng 23(2):239–251MathSciNetCrossRefMATH

Ugander J, Backstrom L, Kleinberg J (2013) Subgraph frequencies: mapping the empirical and extremal geography of large graph collections. In: WWW, pp 1307–1318

Volkovich Y, Litvak N, Donato D (2007) Determining factors behind the PageRank log-log plot. In: Algorithms and models for the web-graph. Springer, pp 108–123

Watts DJ, Strogatz SH (1998) Collective dynamics of ‘small-world’ networks. Nature 393(440–442):26

Weichsel PM (1962) The Kronecker product of graphs. Proc Am Math Soc 13(1):47–52MathSciNetCrossRefMATH

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

Zachary WW (1977) An information flow model for conflict and fission in small groups. J Anthropol Res 33(4):452–473

Zhan Y (2003) Tools for graph mining. Masters thesis, Carnegie Mellon University

Titel: Striations in PageRank-ordered matrices
verfasst von: Corey Pennycuff
Tim Weninger
Publikationsdatum: 01.12.2016
Verlag: Springer Vienna
Erschienen in: Social Network Analysis and Mining / Ausgabe 1/2016
Print ISSN: 1869-5450
Elektronische ISSN: 1869-5469
DOI: https://doi.org/10.1007/s13278-016-0339-8

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 1/2016

Unsupervised graph-based pattern extraction for multilingual emotion classification

Spatiotemporal social (STS) data model: correlating social networks and spatiotemporal data

CADIVa: cooperative and adaptive decentralized identity validation model for social networks

Parallel collective factorization for modeling large heterogeneous networks

An empirical comparison of Big Graph frameworks in the context of network analysis

The social role of social media: the case of Chennai rains-2015

Premium Partner