Regularity Index of Uncertain Random Graph

Lin Chen, Li Zeng, Jin Peng, Junren Ming, Xianghui ZhuSymmetry 2023 · DOI

TL;DR

This paper introduces the concepts of k-regularity and regularity indices for "uncertain random graphs" (URGs), which combine probabilistic and uncertain elements in their edges. The authors develop a method and an algorithm to compute these indices, providing a new way to quantify the regularity of complex networks where information is inherently incomplete or subjective.

What Problem Does This Paper Address?

Real-world networks, such as social networks and transportation systems, often exhibit uncertainty and randomness in their connections. Traditional graph theory, which assumes deterministic relationships, struggles to model these complexities. While random graphs (edges with probabilities) and uncertain graphs (edges with belief degrees) have been studied, systems with both probabilistic and uncertain edge information are less explored. This paper addresses the need to quantify a fundamental graph property – regularity (where all vertices have the same degree) – in these "uncertain random graphs" (URGs). Specifically, it aims to define and compute measures of how likely an URG is to be k-regular or generally regular, especially when dealing with information asymmetry.

Methods

The core of this paper lies in extending graph theory concepts to the realm of uncertain random graphs within the framework of "chance theory."

  • Uncertain Random Graph (URG) Definition: The authors define an URG as a system with vertices, uncertain edges, random edges, and an uncertain random adjacency matrix that captures the likelihood (either probabilistic or uncertain measure) of an edge existing between any two vertices.
  • K-Regularity and Regularity Functions: They introduce boolean functions, $R_k(E(G))$ and $R(E(G))$, that indicate whether a specific realization of the graph is k-regular or regular, respectively.
  • K-Regularity and Regularity Indices: To quantify the likelihood of these properties, they define the k-regularity index ($\mu_k(G)$) and the regularity index ($\mu(G)$) as the "chance measure" (a concept from chance theory) that the graph is k-regular or regular, respectively. This essentially means calculating the probability or belief degree that the graph satisfies these conditions.
  • Computational Formulas: The paper derives theoretical formulas for calculating these indices, involving summations and products over possible edge configurations and their associated probabilities/uncertainty measures.
  • Adjacency Matrix-Based Algorithm: A practical, adjacency matrix-based algorithm is proposed to compute the k-regularity index of an URG. This algorithm systematically iterates through possible graph realizations and calculates the relevant indices.

Datasets

Not discussed in the paper. The paper focuses on theoretical definitions and algorithmic development, illustrated with self-generated examples.

Key Insights and Ideas

  • Unifying Uncertainty and Randomness: The paper provides a formal framework for dealing with graphs that simultaneously exhibit both probabilistic (random) and subjective (uncertain) edge information, which is crucial for modeling many real-world scenarios.
  • Quantifying Regularity in Uncertainty: Defining "regularity indices" allows for a probabilistic or belief-based measure of how "regular" a complex, uncertain network is, moving beyond binary deterministic assessments.
  • Relationship Between Indices: A key finding is that the overall regularity index of an URG is simply the sum of its k-regularity indices for all possible degrees k. This simplifies the understanding of overall regularity.
  • Algorithmic Approach: The development of an adjacency matrix-based algorithm makes the computation of these indices practical, especially for graphs of moderate size.

Key Results

The paper presents several theorems and a corollary:

  • Theorem 2 & 4: Provide formulas for calculating the k-regularity index and regularity index of an URG, respectively, under the assumption of independent edges.
  • Theorem 3 & 5: Offer alternative formulas for the k-regularity index and regularity index, respectively, which are more directly applicable for computation.
  • Corollary 1: Establishes that the regularity index of an URG is the sum of its k-regularity indices.
  • Algorithm 1: An adjacency matrix-based algorithm is presented to compute the k-regularity index.
  • Numerical Examples: Three examples are provided to illustrate the application of the proposed methods and algorithm, demonstrating the calculation of regularity indices for URGs of different orders and sizes. For instance, in Example 1, the regularity index $\mu(G)$ was found to be 0.32.

Limitations and Future Work

  • Computational Complexity: While an algorithm is provided, the complexity of computing these indices for very large graphs is likely to be a significant challenge, as it involves iterating through many possible edge configurations.
  • Assumptions: The theorems often rely on the assumption that edges are independent, which may not always hold in real-world networks.
  • Future Directions: The authors suggest several avenues for future research:
  • Studying the degree sequence of URGs and its properties.
  • Investigating the diameter distribution function of URGs.
  • Developing more efficient algorithms for computing regularity indices for larger-scale URGs.
  • Exploring applications of URGs in social networks and transportation, and their connection with symmetry.

Summary updated

BibTeX
@article{chen2023regularity,
  author = {Lin Chen and Li Zeng and Jin Peng and Junren Ming and Xianghui Zhu},
  title = {{Regularity Index of Uncertain Random Graph}},
  journal = {Symmetry},
  year = {2023},
  doi = {10.3390/sym15010137},
}
Figure