nach oben

Social Network Analysis and Mining

Erschienen in:

01.12.2016 | Original Article

Motif detection speed up by using equations based on the degree sequence

verfasst von: Wolfgang E. Schlauch, Katharina A. Zweig

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

To identify so-called network motifs, the fixed degree sequence model (fdsm) is usually used. For any real-world network, the fdsm is defined as the set of all graphs with the same degree sequence that do not have multiple edges between nodes or self-loops. A subgraph is called a network motif if it occurs statistically significantly often compared to its expected occurrence in the model. However, approximating this value by sampling from the fdsm is computationally expensive and does not scale for large networks. Thus, in this article, we propose a set of equations, based on the degree sequence and a simple independence assumption, to estimate the occurrence of a set of subgraphs in the fdsm. Based on a range of real-world networks, we show that these equations approximate the values in the fdsm very well, except only two data sets. We then propose an efficient way to characterize those data sets in which the equations can be used as an approximation to the fdsm.

Vorheriger Artikel Parallel collective factorization for modeling large heterogeneous networks

Nächster Artikel Unveiling mobility complexity through complex network analysis

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

http://www.weizmann.ac.il/mcb/UriAlon/e-coli-transcription-network.

For further information see http://pil.phys.uniroma1.it/~gcalda/cosinsite/extra/data/foodwebs/WEB.html.

http://wws.weizmann.ac.il/mcb/UriAlon/download/collection-complex-networks.

Aiello W, Graham FC, Lu L (2001) A random graph model for power law graphs. Exp Math 10(1):53–66MathSciNetCrossRefMATH

Bender EA, Canfield ER (1978) The asymptotic number of labeled graphs with given degree sequences. J Comb Theory A 24(3):296–307MathSciNetCrossRefMATH

Berger A, Müller-Hannemann M (2010) Uniform sampling of digraphs with a fixed degree sequence. Graph theoretic concepts in computer science. Springer, New York, pp 220–231CrossRef

Blitzstein J, Diaconis P (2011) A sequential importance sampling algorithm for generating random graphs with prescribed degrees. Internet Math 6(4):489–522MathSciNetCrossRefMATH

Bollobás B (1980) A probabilistic proof of an asymptotic formula for the number of labelled regular graphs. Eur J Comb 1(4):311–316MathSciNetCrossRefMATH

Brualdi RA (1980) Matrices of zeros and ones with fixed row and column sum vectors. Linear Algebra Appl 33:159–231MathSciNetCrossRefMATH

Chung F, Lu L (2002) Connected components in random graphs with given degree sequences. Ann Comb 6:125–145MathSciNetCrossRefMATH

Del Genio CI, Kim H, Toroczkai Z, Bassler KE (2010) Efficient and exact sampling of simple graphs with given arbitrary degree sequence. PLoS One 5(4):e10,012CrossRef

Erdős PL, Miklós I, Toroczkai Z (2010) A simple Havel-Hakimi type algorithm to realize graphical degree sequences of directed graphs. Electron J Comb 17(1):R66MathSciNetMATH

Gigerenzer G (2004) Mindless statistics. J Soc Econ 33(5):587–606CrossRef

Gkantsidis C, Mihail M, Zegura E (2003) The markov chain simulation method for generating connected power law random graphs. In: SIAM Alenex

Goodman LA (1962) The variance of the product of k random variables. J Am Stat Assoc 57(297): 54–60. http://www.jstor.org/stable/2282440

Goodman LA (1960) On the exact variance of products. J Am Stat Assoc 55(292):708–713. doi:10.1080/01621459.1960.10483369 MathSciNetCrossRefMATH

Janson S (2013) The probability that a random multigraph is simple, ii

Janson S (2009) The probability that a random multigraph is simple. Comb Probab Comput 18(1–2):205–225MathSciNetCrossRefMATH

Kashtan N, Itzkovitz S, Milo R, Alon U (2004) Efficient sampling algorithm for estimating subgraph concentrations and detecting network motifs. Bioinformatics 20(11):1746–1758CrossRef

Kim H, Genio CID, Bassler KE, Toroczkai Z (2012) Constructing and sampling directed graphs with given degree sequences. New J Phys 14(2):023,012CrossRef

Klymko C, Gleich DF, Kolda TG (2014) Using triangles to improve community detection in directed networks. In: The second ASE international conference on big data science and computing, BigDataScience

Kolmogorov AN (1933) Sulla determinazione empirica di una legge di distribuzione. na

Lancichinetti A, Fortunato S, Kertész J (2009) Detecting the overlapping and hierarchical community structure in complex networks. New J Phys 11(3):033,015CrossRef

Leskovec, J, Krevl A (2014) SNAP datasets: stanford large network dataset collection. http://snap.stanford.edu/data

Milo R, Shen-Orr S, Itzkovitz S, Kashtan N, Chklovskii D, Alon U (2002) Network motifs: simple building blocks of complex networks. Science 298(5594):824–827CrossRef

Milo R, Itzkovitz S, Kashtan N, Levitt R, Shen-Orr S, Ayzenshtat I, Sheffer M, Alon U (2004) Superfamilies of evolved and designed networks. Science 303(5663):1538–1542CrossRef

Milo R, Kashtan N, Itzkovitz S, Newman, MEJ, Alon, U (2003) On the uniform generation of random graphs with prescribed degree sequences. arXiv preprint cond-mat/0312028

Moore C, Newman MEJ (2000) Epidemics and percolation in small-world networks. http://arxiv.org/abs/cond-mat/9911492

Newman ME (2005) Power laws, pareto distributions and zipf’s law. Contemp Phys 46: 323–351. http://arxiv.org/abs/cond-mat/0412004

Newman ME, Strogatz SH, Watts DJ (2001) Random graphs with arbitrary degree distributions and their applications. Phys Rev E Stat Nonlin Soft Matter Phys 64(2 Pt 2). http://view.ncbi.nlm.nih.gov/pubmed/11497662

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

Newman ME, Watts DJ, Strogatz SH (2002) Random graph models of social networks. Proc Natl Acad Sci USA 99:2566–2572CrossRefMATH

Newman ME (2003) Mixing patterns in networks. Phys Rev E 67(2):026126. doi:10.1103/physreve.67.026126 MathSciNetCrossRef

Newman MEJ (2003) The structure and function of complex networks. SIAM Rev 45:167–256MathSciNetCrossRefMATH

Newman M (2010) Networks: an introduction. Oxford University Press, OxfordCrossRefMATH

Newman MEJ, Girvan M (2004) Finding and evaluating community structure in networks. Phys Rev E 69:026113

Ray J, Pinar A, Seshadhri C (2012) Are we there yet? when to stop a markov chain while generating random graphs. In: Bonato A, Janssen J (eds) Algorithms and Models for the Web Graph, vol 7323., Lecture Notes in Computer ScienceSpringer, Berlin Heidelberg, pp 153–164CrossRef

Ryser HJ (1957) Combinatorial properties of matrices of zeros and ones. Can J Math 9:371–377MathSciNetCrossRefMATH

Schlauch WE, Horvát EÁ, Zweig KA (2015) Different flavors of randomness: comparing random graph models with fixed degree sequences. Soc Netw Anal Min 5(1):1–14CrossRef

Shen H, Cheng X, Cai K, Hu MB (2009) Detect overlapping and hierarchical community structure in networks. Phys A Stat Mech Appl 388(8):1706–1712CrossRef

Van Der Hofstad R (2009) Random graphs and complex networks. http://www.win.tue.nl/rhofstad/NotesRGCN.pdf

Viger F, Latapy M (2005) Efficient and simple generation of random simple connected graphs with prescribed degree sequence. Computing and Combinatorics. Springer, New York, pp 440–449CrossRef

Wang J, Tsang WW, Marsaglia G (2003) Evaluating kolmogorov’s distribution. J Stat Softw 8(18):1–14

Wilson J (1987) Methods for detecting non-randomness in species co-occurrences: a contribution. Oecologia 73(4):579–582CrossRef

Zweig KA (2010) How to forget the second side of the story: a new method for the one-mode projection of bipartite graphs. In: Proceedings of the 2010 international conference on advances in social networks analysis and mining ASONAM 2010, pp. 200–207

Zweig KA, Kaufmann M (2011) A systematic approach to the one-mode projection of bipartite graphs. Soc Netw Anal Min 1(3):187–218CrossRef

Titel: Motif detection speed up by using equations based on the degree sequence
verfasst von: Wolfgang E. Schlauch
Katharina A. Zweig
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-0357-6

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

Notice to: Promoting where, when and what? An analysis of web logs by integrating data mining and social network techniques to guide ecommerce business promotions

On the prevalence of hierarchies in social networks

Striations in PageRank-ordered matrices

Supporting geospatial privacy-preserving data mining of social media

Quality of life: a social network’s perspective

Unsupervised graph-based pattern extraction for multilingual emotion classification