Abstract: On-line social networks, such as in Facebook and Twitter, are often studied from the perspective of friendship ties between agents in the network. Adversarial ties, however, also play an important role in the structure and function of social networks, but are often hidden. Underlying generative mechanisms of social networks are predicted by structural balance theory, which postulates that triads of agents, prefer to be transitive, where friends of friends are more likely friends, or anti-transitive, where adversaries of adversaries become friends. The previously proposed Iterated Local Transitivity (ILT) and Iterated Local Anti-Transitivity (ILAT) models incorporated transitivity and anti-transitivity, respectively, as evolutionary mechanisms. These models resulted in graphs with many observable properties of social networks, such as low diameter, high clustering, and densification. We propose a new, generative model, referred to as the Iterated Local Model (ILM) for social networks synthesizing both transitive and anti-transitive triads over time. In ILM, we are given a countably infinite binary sequence as input, and that sequence determines whether we apply a transitive or an anti-transitive step. The resulting model exhibits many properties of complex networks observed in the ILT and ILAT models. In particular, for any input binary sequence, we show that asymptotically the model generates finite graphs that densify, have clustering coefficient bounded away from 0, have diameter at most 3, and exhibit bad spectral expansion. We also give a thorough analysis of the chromatic number, domination number, Hamiltonicity, and isomorphism types of induced subgraphs of ILM graphs.
Recommendations
- The iterated local directed transitivity model for social networks
- Iterated local transitivity model for signed social networks
- A local structure model for network analysis
- Iterated global models for complex networks
- Local matching dynamics in social networks
- Local matching dynamics in social networks
- Information diffusion on the iterated local transitivity model of online social networks
- A local-world evolving network model
- Constructing algebraic models for local social networks using statistical methods
- Random graph models of social networks
Cites work
- scientific article; zbMATH DE number 964896 (Why is no real title available?)
- A Dynamic Model for On-Line Social Networks
- A course on the web graph
- A spatial web graph model with local influence regions
- Dynamic Competition Networks: Detecting Alliances and Leaders
- Emergence of Scaling in Random Networks
- Geometric protean graphs
- High-dimensional Apollonian networks
- How to Burn a Graph
- Information diffusion on the iterated local transitivity model of online social networks
- Large networks and graph limits
- Models of online social networks
- Networks, crowds and markets. Reasoning about a highly connected world.
- The degree sequence of a scale-free random graph process
Cited in
(13)- A local structure model for network analysis
- 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 iterative independent model
- Information diffusion on the iterated local transitivity model of online social networks
- The frustum network model based on clique extension
- Transitivity model on signed graphs
- Iterated local transitivity model for signed social networks
- Models of online social networks
- The iterated local transitivity model for hypergraphs
- The iterated local directed transitivity model for social networks
- Iterated global models for complex networks
This page was built for publication: The iterated local model for social networks
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q777439)
