Clique percolation in random graphs

Ming Li, Youjin Deng, and Bing-Hong Wang
Phys. Rev. E 92, 042116 – Published 7 October 2015

Abstract

As a generation of the classical percolation, clique percolation focuses on the connection of cliques in a graph, where the connection of two k cliques means that they share at least l<k vertices. In this paper we develop a theoretical approach to study clique percolation in Erdős-Rényi graphs, which gives not only the exact solutions of the critical point, but also the corresponding order parameter. Based on this, we prove theoretically that the fraction ψ of cliques in the giant clique cluster always makes a continuous phase transition as the classical percolation. However, the fraction ϕ of vertices in the giant clique cluster for l>1 makes a step-function-like discontinuous phase transition in the thermodynamic limit and a continuous phase transition for l=1. More interesting, our analysis shows that at the critical point, the order parameter ϕc for l>1 is neither 0 nor 1, but a constant depending on k and l. All these theoretical findings are in agreement with the simulation results, which give theoretical support and clarification for previous simulation studies of clique percolation.

  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Received 11 August 2015

DOI:https://doi.org/10.1103/PhysRevE.92.042116

©2015 American Physical Society

Physics Subject Headings (PhySH)

Statistical Physics & ThermodynamicsNetworks

Authors & Affiliations

Ming Li1, Youjin Deng1,2, and Bing-Hong Wang1

  • 1Department of Modern Physics, University of Science and Technology of China, Hefei 230026, People's Republic of China
  • 2Hefei National Laboratory for Physical Sciences at Microscale, University of Science and Technology of China, Hefei 230026, People's Republic of China

Article Text (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand
Issue

Vol. 92, Iss. 4 — October 2015

Reuse & Permissions
Access Options
Author publication services for translation and copyediting assistance advertisement

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review E

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×