The iterated local transitivity model for hypergraphs

DOI10.1016/J.DAM.2023.04.006MaRDI QIDQ6162030zbMATH OpenOpenAlexFDO

Authors Natalie C. Behague, Anthony Bonato, Melissa Huggan, Rehan Malik, Trent Gregory Marbach

Publication date 15 June 2023

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2101.12560

zbMATH Keywords

2-sectionclustering coefficienthypergraphsmotifstransitivity

Mathematics Subject Classification ID

Hypergraphs (05C65) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Social networks; opinion dynamics (91D30)

Abstract: Complex networks are pervasive in the real world, capturing dyadic interactions between pairs of vertices, and a large corpus has emerged on their mining and modeling. However, many phenomena are comprised of polyadic interactions between more than two vertices. Such complex hypergraphs range from emails among groups of individuals, scholarly collaboration, or joint interactions of proteins in living cells. A key generative principle within social and other complex networks is transitivity, where friends of friends are more likely friends. The previously proposed Iterated Local Transitivity (ILT) model incorporated transitivity as an evolutionary mechanism. The ILT model provably satisfies many observed properties of social networks, such as densification, low average distances, and high clustering coefficients. We propose a new, generative model for complex hypergraphs based on transitivity, called the Iterated Local Transitivity Hypergraph (or ILTH) model. In ILTH, we iteratively apply the principle of transitivity to form new hypergraphs. The resulting model generates hypergraphs simulating properties observed in real-world complex hypergraphs, such as densification and low average distances. We consider properties unique to hypergraphs not captured by their 2-section. We show that certain motifs, which are specified subhypergraphs of small order, have faster growth rates in ILTH hypergraphs than in random hypergraphs with the same order and expected average degree. We show that the graphs admitting a homomorphism into the 2-section of the initial hypergraph appear as induced subgraphs in the 2-section of ILTH hypergraphs. We consider new and existing hypergraph clustering coefficients, and show that these coefficients have larger values in ILTH hypergraphs than in comparable random hypergraphs.

Recommendations

• The iterated local model for social networks
• The iterated local directed transitivity model for social networks
• A Dynamic Model for On-Line Social Networks
• Models of online social networks
• Iterated local transitivity model for signed social networks

Cites work

• A course on the web graph
• A Dynamic Model for On-Line Social Networks
• Complex graphs and networks
• scientific article; zbMATH DE number 3758364 (Why is no real title available?)
• scientific article; zbMATH DE number 43754 (Why is no real title available?)
• scientific article; zbMATH DE number 2117181 (Why is no real title available?)
• Information diffusion on the iterated local transitivity model of online social networks
• Models of online social networks
• Networks, crowds and markets. Reasoning about a highly connected world.
• The iterated local directed transitivity model for social networks
• The iterated local model for social networks

Cited in

(6)

• The iterated local directed transitivity model for social networks
• Iterated global models for complex networks
• Common adversaries form alliances: modelling complex networks via anti-transitivity
• The iterated local transitivity model for tournaments
• An evolving network model from clique extension
• The frustum network model based on clique extension

This page was built for publication: The iterated local transitivity model for hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6162030)