The iterated local model for social networks

DOI10.1016/J.DAM.2020.04.018zbMATH Open1444.91173arXiv1903.04523OpenAlexW3023014138MaRDI QIDQ777439FDOQ777439

Authors: Anthony Bonato, H. Chuangpishit, Sean English, Bill Kay, Erin Meger 

Publication date: 7 July 2020

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

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.

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

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

zbMATH Keywords

social networkstransitivitydomination numberclustering coefficientHamiltonian graphspectral expansiondensificationanti-transitivity

Mathematics Subject Classification ID

Applications of graph theory (05C90) Social networks; opinion dynamics (91D30)

Cites Work

• Large networks and graph limits
• Title not available (Why is that?)
• Emergence of Scaling in Random Networks
• Networks, crowds and markets. Reasoning about a highly connected world.
• The degree sequence of a scale-free random graph process
• Information diffusion on the iterated local transitivity model of online social networks
• A Dynamic Model for On-Line Social Networks
• A course on the web graph
• A spatial web graph model with local influence regions
• How to Burn a Graph
• Geometric protean graphs
• High-dimensional Apollonian networks
• Models of online social networks
• Dynamic Competition Networks: Detecting Alliances and Leaders

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
• The iterated local transitivity model for hypergraphs
• Models of online social networks
• 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)