A Survey of Measures for Network Motifs

Feng Xia, Haoran Wei, Shuo Yu, Da Zhang, Bo Xu

Abstract

Network motifs represent the recurring, functional building blocks of complex networks. While numerous algorithms exist for motif detection, a systematic framework for measuring and evaluating these patterns has been lacking. This paper provides a comprehensive survey of motif measures, categorizing them into structural and statistical groups. By organizing these metrics, the authors offer a roadmap for researchers to move beyond simple detection toward sophisticated network classification, community detection, and evolutionary computing.

Introduction: The Meso-Level of Complex Networks

In the study of complex systems—ranging from biological gene regulation to technological power grids—analysis typically occurs at the "micro" level (individual nodes) or the "macro" level (global properties like average path length). However, a crucial meso-level structure exists: the network motif. These are small patterns of interconnections that appear significantly more frequently than would be expected by chance, acting as the functional "Lego bricks" of a system.

Visual representation of network motifs (a) and their occurrence within a larger network structure (b).

While finding these motifs is a well-studied algorithmic problem, quantifying their importance and comparing them across different domains requires standardized measures. This paper fills this gap by organizing the scattered literature into a cohesive framework for motif evaluation.

Taxonomy of Motif Measures

The authors propose a two-tier classification system to organize motif measures, distinguishing between those that evaluate internal topology and those that rely on statistical comparison against null models.

Flowchart illustrating the survey's categorization of motif measures into structural and statistical groups alongside applications and challenges.

Structural Measures

Structural measures focus on the topology and relative importance of motifs within the network's architecture. These metrics are particularly useful for understanding how motifs contribute to the overall connectivity and robustness of a system. Key examples include:

  • Motif-based Node/Edge Degree: Quantifies the participation of specific nodes or edges in various motifs, identifying key structural components.
  • Supernetwork Motif Entropy (SNME): Measures the complexity of "supernetworks" composed of interconnected motifs.
  • Motif-based Conductance ($\phi_M$): Evaluates how effectively motifs can be used to partition a network, making it a superior tool for community detection.

Statistical Measures

Statistical measures compare motif frequency in a real-world network against a "null model"—a randomized version of the same network that preserves certain basic properties. These are the gold standard for network classification. Essential metrics include:

  • Z-score and P-value: Standard statistical tests for over-representation.
  • Significance Profile (SP): A normalized vector that allows researchers to compare the motif fingerprints of networks of vastly different sizes.
  • Subgraph Ratio Profile (SRP): A more robust alternative to the Z-score for real-world networks that do not follow Gaussian distributions.
  • Motif Difficulty (MD): A specialized measure used in evolutionary computing to predict the complexity of a search space.

Key Insights and Applications

One of the most striking insights highlighted in the survey is the "Superfamily" Phenomenon. Unrelated networks—such as the World Wide Web and certain social networks—can share almost identical Significance Profiles. This suggests they belong to the same "superfamily" and share underlying structural design principles despite their different origins. By analyzing 3-motif and 4-motif profiles across biological, social, and technological domains, researchers can classify networks into categories (e.g., "food webs" vs. "sensory transcription") with high accuracy.

Furthermore, the paper emphasizes the need to bridge the gap between statistical significance (how often a motif appears) and functional significance (what role it actually plays in the system's operation). A motif might be statistically rare but functionally vital to the network's survival.

Challenges and Future Directions

Despite the advancement of motif measures, the field faces several ongoing challenges:

  • Computational Complexity: Motif detection is an NP-hard problem. As motifs grow in size (e.g., subgraphs with more than 10 nodes), the computational cost becomes astronomical.
  • Null Model Selection: The validity of statistical measures depends entirely on the quality of the randomized null model. If the model is poorly constructed, the resulting measures will be misleading.
  • Dynamic and Temporal Motifs: Most current research assumes networks are static. Developing measures for motifs that change over time is a critical frontier for the field.
  • Higher-Order Complexity: There is a growing need to study how different motifs interact with one another, rather than treating each motif as an isolated structural unit.

Summary updated

Abstract

Network motifs provide an enlightening insight into uncovering the structural design principles of complex networks across multifarious disciplines, such as physics, biology, social science, engineering, and military science. Measures for network motifs play an indispensable role in the procedures of motif measurement and evaluation which are crucial steps in motif detection, counting, and clustering. However, there is a relatively small body of literature concerned with measures for network motifs. In this paper, we review the measures for network motifs in two categories: structural measures and statistical measures. The application scenarios for each measure and the distinctions of measures in similar scenarios are also summarized. We also conclude the challenges for using these measures and put forward some future directions on this topic. Overall, the objective of this survey is to provide an overview of motif measures, which is anticipated to shed light on the theory and practice of complex networks.
BibTeX
@article{xia2019survey,
  author = {Feng Xia and Haoran Wei and Shuo Yu and Da Zhang and Bo Xu},
  title = {{A Survey of Measures for Network Motifs}},
  journal = {IEEE Access},
  year = {2019},
  doi = {10.1109/access.2019.2926752},
}
Figure