Large dicliques in a directed inhomogeneous random graph

Abstract

Our main interest in this paper is the large dicliques in a directed inhomogeneous random graph model G(n,α, Φ) on n vertices, which has power-law out/in-degree distributions with scaling exponent α>0 and community structures involved in the homophyly matrix Φ. We show that there is a major difference in the size of the largest diclique ω ^d (G(n,α, Φ)) between the case α<2 and α>2 with an intermediate result for α=2. In addition, we show that a simple algorithm with high probability finds a large diclique of size ω ^d (G(n,α, Φ)) in a polynomial time. Our simulation results reveal that the connections between different subcommunities are essential for the formation of large clusters in the networks.

Keywords:

• diclique
• inhomogeneous random graph
• community
• greedy algorithm

2010 AMS Subject Classifications:

• 05C69
• 60C05
• 05C80

Acknowledgements

The author is grateful to the anonymous referees for their instructive and detailed comments towards the improvement of this paper.