A Dynamic Model for On-Line Social Networks

DOI10.1007/978-3-540-95995-3_11MaRDI QIDQ3601176zbMATH OpenOpenAlexFDO

Authors Anthony Bonato, Noor Hadi, Paul Horn, Paweł Prałat, Changping Wang

Publication date 10 February 2009

Published in Algorithms and Models for the Web-Graph (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Internet topics (68M11) Social networks; opinion dynamics (91D30)

Abstract: We present a deterministic model for on-line social networks (OSNs) based on transitivity and local knowledge in social interactions. In the Iterated Local Transitivity (ILT) model, at each time-step and for every existing node $x$, a new node appears which joins to the closed neighbour set of $x.$ The ILT model provably satisfies a number of both local and global properties that were observed in OSNs and other real-world complex networks, such as a densification power law, decreasing average distance, and higher clustering than in random graphs with the same average degree. Experimental studies of social networks demonstrate poor expansion properties as a consequence of the existence of communities with low number of inter-community edges. Bounds on the spectral gap for both the adjacency and normalized Laplacian matrices are proved for graphs arising from the ILT model, indicating such bad expansion properties. The cop and domination number are shown to remain the same as the graph from the initial time-step $G_0$, and the automorphism group of $G_0$ is a subgroup of the automorphism group of graphs generated at all later time-steps. A randomized version of the ILT model is presented, which exhibits a tuneable densification power law exponent, and maintains several properties of the deterministic model.

Recommendations

• Models of online social networks
• A dynamic model of social network formation
• A dynamic model of network formation
• Stability analysis of an online social network model
• scientific article; zbMATH DE number 7731189
• A network social interaction model with heterogeneous links

Cited in

(19)

• Iterated local transitivity model for signed social networks
• A hybrid human dynamics model on analyzing hotspots in social networks
• Generating graphs by creating associative and random links between existing nodes
• Transitivity model on signed graphs
• Information diffusion on the iterated local transitivity model of online social networks
• Geometric protean graphs
• The geometric protean model for on-line social networks
• On the mixing time of geographical threshold graphs
• A dynamic model of social network formation
• 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
• Models of online social networks
• A dynamic model of network formation
• The iterated local transitivity model for tournaments
• The iterative independent model
• Stability analysis of an online social network model
• The iterated local transitivity model for hypergraphs
• The iterated local model for social networks

This page was built for publication: A Dynamic Model for On-Line Social Networks

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