Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
DE
EN
Books
Journals
Events
Topic Page
Marketing
Log in
Learn more about individual access
Request company access
13th International Engine Congress 2026 | 24 + 25 February 2026

Meeting Place for the Powertrain and Sustainable Fuels Community

Take part as a speaker in the 13th International Engine Congress 2026, the Meeting Place for the Powertrain, and Sustainable Fuels Community for the exchange of experience. Submit a subject proposal online about our main subject areas: Passenger car engine technology, Commercial vehicle engine technology and Sustainable Fuels & Energy!
EXTENDED SEARCH
Log in
Top
Social Network Analysis and Mining
Published in:

01-12-2016 | Original Article

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

Authors: Wolfgang E. Schlauch, Katharina A. Zweig

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

Log in

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

search-config
loading …

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.
previous article Parallel collective factorization for modeling large heterogeneous networks
next article Unveiling mobility complexity through complex network analysis

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
Footnotes
Literature
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
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
Gkantsidis C, Mihail M, Zegura E (2003) The markov chain simulation method for generating connected power law random graphs. In: SIAM Alenex
Janson S (2013) The probability that a random multigraph is simple, ii
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
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
Newman ME, Watts DJ, Strogatz SH (2002) Random graph models of social networks. Proc Natl Acad Sci USA 99:2566–2572CrossRefMATH
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
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
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
Metadata
Title
Motif detection speed up by using equations based on the degree sequence
Authors
Wolfgang E. Schlauch
Katharina A. Zweig
Publication date
01-12-2016
Publisher
Springer Vienna
Published in
Social Network Analysis and Mining / Issue 1/2016
Print ISSN: 1869-5450
Electronic ISSN: 1869-5469
DOI
https://doi.org/10.1007/s13278-016-0357-6

Other articles of this Issue 1/2016

Social network ad allocation and optimization: a geometric mapping-based approach

  • Original Article

Multi-source models for civil unrest forecasting

  • Original Article

Using geolocated tweets for characterization of Twitter in Portugal and the Portuguese administrative regions

  • Original Article

Network topology and mean infection times

  • Original Article

Individual privacy in social influence networks

  • Original Article

Reducing seed noise in personalized PageRank

  • Original Article

Premium Partner

    Image Credits