Maximum matchings in scale-free networks with identical degree distribution
From MaRDI portal
Publication:528496
DOI10.1016/J.TCS.2017.02.027zbMATH Open1370.68233arXiv1703.09041OpenAlexW2592053950MaRDI QIDQ528496FDOQ528496
Publication date: 12 May 2017
Published in: Theoretical Computer Science (Search for Journal in Brave)
Abstract: The size and number of maximum matchings in a network have found a large variety of applications in many fields. As a ubiquitous property of diverse real systems, power-law degree distribution was shown to have a profound influence on size of maximum matchings in scale-free networks, where the size of maximum matchings is small and a perfect matching often does not exist. In this paper, we study analytically the maximum matchings in two scale-free networks with identical degree sequence, and show that the first network has no perfect matchings, while the second one has many. For the first network, we determine explicitly the size of maximum matchings, and provide an exact recursive solution for the number of maximum matchings. For the second one, we design an orientation and prove that it is Pfaffian, based on which we derive a closed-form expression for the number of perfect matchings. Moreover, we demonstrate that the entropy for perfect matchings is equal to that corresponding to the extended Sierpi'nski graph with the same average degree as both studied scale-free networks. Our results indicate that power-law degree distribution alone is not sufficient to characterize the size and number of maximum matchings in scale-free networks.
Full work available at URL: https://arxiv.org/abs/1703.09041
Recommendations
Graph theory (including graph drawing) in computer science (68R10) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- Emergence of Scaling in Random Networks
- The Structure and Function of Complex Networks
- Collective dynamics of ‘small-world’ networks
- Matching theory
- Generalized domino-shuffling.
- The statistics of dimers on a lattice. I: The number of dimer arrangements on a quadratic lattice
- The Tower of Hanoi – Myths and Maths
- Dimer problem in statistical mechanics-an exact result
- Crossing numbers of Sierpiński‐like graphs
- The complexity of computing the permanent
- Dimers and amoebae
- The Complexity of Enumeration and Reliability Problems
- Title not available (Why is that?)
- Applications of graphical condensation for enumerating matchings and tilings
- A quadratic identity for the number of perfect matchings of plane graphs
- Title not available (Why is that?)
- Inverted Berezinskii-Kosterlitz-Thouless singularity and high-temperature algebraic order in an Ising model on a scale-free hierarchical-lattice small-world network
- Structural properties of subdivided-line graphs
- DIMERS ON TWO-DIMENSIONAL LATTICES
- Local characteristics, entropy and limit theorems for spanning trees and domino tilings via transfer-impedances
- Unique maximum matching algorithms
- Graphical condensation for enumerating perfect matchings
- Graphical condensation of plane graphs: a combinatorial approach
- On the theory of Pfaffian orientations. I: Perfect matchings and permanents
- The number of matchings in random graphs
- Maximum matching in multi-interface networks
- Maximum matching in regular and almost regular graphs
- Enumeration of perfect matchings of a type of Cartesian products of graphs
- Exact and asymptotic enumeration of perfect matchings in self-similar graphs
- Counting dimer coverings on self-similar Schreier graphs
- Pfaffian orientation and enumeration of perfect matchings for some Cartesian products of graphs
- On the number of perfect matchings of line graphs
- A box-covering algorithm for fractal scaling in scale-free networks
- Controllability and matchings in random bipartite graphs
- The number and degree distribution of spanning trees in the Tower of Hanoi graph
- Number of maximum matchings of bipartite graphs with positive surplus
- Applications of perfect matchings in chemistry
- A new NC-algorithm for finding a perfect matching in bipartite planar and small genus graphs (extended abstract)
- Finding a maximum matching in a sparse random graph in O ( n ) expected time
- Title not available (Why is that?)
- Farey graphs as models for complex networks
Cited In (2)
This page was built for publication: Maximum matchings in scale-free networks with identical degree distribution
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q528496)
