Clique structure and other network properties of the tensor product of Erdős–Rényi graphs

Işlak Ü., İncekara B.

Brazilian Journal of Probability and Statistics, cilt.39, sa.2, ss.185-203, 2025 (SCI-Expanded, Scopus) identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 39 Sayı: 2
  • Basım Tarihi: 2025
  • Doi Numarası: 10.1214/25-bjps630
  • Dergi Adı: Brazilian Journal of Probability and Statistics
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus, zbMATH
  • Sayfa Sayıları: ss.185-203
  • Anahtar Kelimeler: clique, clustering coefficient, Erdős–Rényi graph, graph product, Random graph
  • Orta Doğu Teknik Üniversitesi Adresli: Evet

Özet

We analyze the number of cliques of given size and the size of the largest clique in tensor product G × H of two Erdős–Rényi graphs G and H. Then an extended clustering coefficient is introduced and is studied for G × H. Restriction to the standard clustering coefficient has a direct relation to the local efficiency of the graph, and the results are also interpreted in terms of the efficiency. As a last statistic of interest, the number of isolated vertices is analyzed for G × H.