Partially ordered sets in complex networks

Qi Xuan, Fang Du, Wu Tie-junJournal of Physics A Mathematical and Theoretical 2010 · DOI

TL;DR

This paper introduces a novel way to analyze complex networks by defining a "partial order" between nodes based on their neighbor sets, leading to the concepts of "chains" and "families." They found that real-world networks exhibit distinct chain length distributions that are not well-explained by existing network models, suggesting a need for new modeling approaches.

What Problem Does This Paper Address?

Traditional network analysis often focuses on individual node properties (like degree) or simple pair-wise relationships. While concepts like "small-world" and "scale-free" properties have been influential, they don't fully capture the nuanced contributions of nodes to network connectivity, especially in complex, real-world systems. The authors aim to develop a more refined method to rank and classify nodes based on their importance for network connectivity, moving beyond simple degree or clustering measures. They also seek to understand the underlying mechanisms that generate the observed structures in real-world networks, which current models struggle to replicate.

Methods

The core of the paper lies in defining a "partial order relation" ($\leq$) between vertices ($v_i \leq v_j$) if the neighbor set of $v_i$ is a subset of the neighbor set of $v_j$ ($U_i \subseteq U_j$). This relation is shown to be reflexive, transitive, and antisymmetric, forming a partially ordered set.

From this, they define:

  • Chains: Maximum linearly ordered subsets of vertices within the network. Essentially, these are sequences of vertices where each vertex's neighbor set is contained within the next.
  • Families: Groups of chains that share the same "end-vertex" (the last vertex in a chain).
  • Chain Graph: A directed graph representing these partial orders, where edges connect vertices in a chain. Redundant edges are removed to simplify the graph.

They then propose new network measurements based on these concepts:

  • Chain length distribution
  • Family diversity distribution
  • Family centrality (implied through discussion of end-vertex importance)

An algorithm is provided to construct the chain graph and extract chains and families.

Datasets

The authors analyze three types of real-world networks:

  1. Protein-protein interaction networks: Giant components from four species (Caenorhabditis elegans (CAE), Saccharomyces cerevisiae (SAC), Homo sapiens (HOM), and Drosophila melanogaster (DRO)) from the BioGrid database.
  2. Autonomous system (AS) relationship networks: Six networks captured at different times from 2004 to 2009 from the CAIDA database.
  3. Friendship network: A network crawled from Douban (a Chinese social networking site) on March 18, 2009.

They also compare these with artificial networks generated by three well-known models:

  • Barabási-Albert (BA) model
  • Local-world (LW) model
  • Dorogovtsev, Mendes, and Samukhin (DMS) model

Key Insights and Ideas

  • Chains as a measure of contribution: The concept of a chain provides a way to understand how nodes contribute to network connectivity. The end-vertex of a chain is particularly important, as it can effectively "replace" other vertices in the chain regarding connectivity contributions.
  • Real-world networks have long chains: Unlike artificial networks generated by standard models, real-world networks exhibit a significant number of long chains. This suggests a structural property not captured by current models.
  • Power-law chain length distribution: The distribution of chain lengths in real-world networks closely follows a power-law, indicating a scale-invariant property. This is a key finding that current models fail to reproduce.
  • Chain-based positive feedback: The authors hypothesize that the long chains and power-law distribution are driven by a "chain-based positive feedback mechanism." This mechanism suggests that new nodes are more likely to join longer chains, potentially due to a preferential attachment rule combined with a structured recommendation process (especially in social networks).
  • Efficient substitution in real-world networks: The relatively high average incoming degree of chain graphs in real-world networks suggests an efficient "substitution mechanism," where nodes can be readily replaced by others in terms of their connectivity role.

Key Results

  • Chain Length Distribution: Real-world networks (protein-protein, AS, Douban) show approximately power-law chain length distributions (P($l_c$) $\sim l_c^{-\alpha}$), with exponents varying across network types. Artificial networks generated by BA, LW, and DMS models have much shorter average chain lengths and do not exhibit this power-law behavior.
  • Family Diversity: Real-world networks generally have higher average family diversity compared to artificial networks. Protein-protein and friendship networks show an exponential-decaying power-law distribution for family diversity, while AS networks show a near power-law.
  • Average Incoming Degree of Chain Graphs: Real-world networks tend to have a higher average incoming degree in their chain graphs compared to artificial networks. The Douban friendship network, in particular, shows the highest (k$_{in}$).

Limitations and Future Work

  • Model Explanations: The paper explicitly states that most of the observed partially ordered set-based properties (especially the power-law chain length distribution) cannot be explained by current well-known scale-free network models (BA, LW, DMS).
  • Need for New Models: The authors conclude that more appropriate network models are required to explain these new properties. They suggest that a quasi-star structure with a densely connected nucleus, as observed in AS networks, might offer some insights into long chains, high diversity, and overlapping families.
  • Further Investigation: The paper calls for further research into developing these new network models.

Summary updated

Abstract

In this paper, a partial-order relation is defined among vertices of a network to describe which vertex is more important than another on its contribution to the connectivity of the network. A maximum linearly ordered subset of vertices is defined as a chain and the chains sharing the same end-vertex are grouped as a family. Through combining the same vertices appearing in different chains, a directed chain graph is obtained. Based on these definitions, a series of new network measurements, such as chain length distribution, family diversity distribution, as well as the centrality of families, are proposed. By studying the partially ordered sets in three kinds of real-world networks, many interesting results are revealed. For instance, the similar approximately power-law chain length distribution may be attributed to a chain-based positive feedback mechanism, i.e. new vertices prefer to participate in longer chains, which can be inferred by combining the notable preferential attachment rule with a well-ordered recommendation manner. Moreover, the relatively large average incoming degree of the chain graphs may indicate an efficient substitution mechanism in these networks. Most of the partially ordered set-based properties cannot be explained by the current well-known scale-free network models; therefore, we are required to propose more appropriate network models in the future.
BibTeX
@article{xuan2010partially,
  author = {Qi Xuan and Fang Du and WU Tie-jun},
  title = {{Partially ordered sets in complex networks}},
  journal = {Journal of Physics A Mathematical and Theoretical},
  year = {2010},
  doi = {10.1088/1751-8113/43/18/185001},
}
Figure