Self-organizing flows in social networks

DOI10.1007/978-3-319-03578-9_10MaRDI QIDQ2868636zbMATH OpenOpenAlexFDO

Authors Nidhi Hegde, Laurent Massoulié, Laurent Viennot

Publication date 17 December 2013

Published in Structural Information and Communication Complexity (Search for Journal in Brave)

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

zbMATH Keywords

price of anarchynetwork formationself-organisationbudget of attentionsocial filtering

Mathematics Subject Classification ID

Social networks; opinion dynamics (91D30) Games involving graphs (91A43)

Abstract: Social networks offer users new means of accessing information, essentially relying on "social filtering", i.e. propagation and filtering of information by social contacts. The sheer amount of data flowing in these networks, combined with the limited budget of attention of each user, makes it difficult to ensure that social filtering brings relevant content to the interested users. Our motivation in this paper is to measure to what extent self-organization of the social network results in efficient social filtering. To this end we introduce flow games, a simple abstraction that models network formation under selfish user dynamics, featuring user-specific interests and budget of attention. In the context of homogeneous user interests, we show that selfish dynamics converge to a stable network structure (namely a pure Nash equilibrium) with close-to-optimal information dissemination. We show in contrast, for the more realistic case of heterogeneous interests, that convergence, if it occurs, may lead to information dissemination that can be arbitrarily inefficient, as captured by an unbounded "price of anarchy". Nevertheless the situation differs when users' interests exhibit a particular structure, captured by a metric space with low doubling dimension. In that case, natural autonomous dynamics converge to a stable configuration. Moreover, users obtain all the information of interest to them in the corresponding dissemination, provided their budget of attention is logarithmic in the size of their interest set.

Recommendations

• Self-organizing flows in social networks
• A game-theoretic model of attention in social networks
• A game theoretic analysis of network design with socially-aware users
• Basic network creation games with communication interests
• On the effects of heterogeneity on one-way flow network formation

Cites work

• A Noncooperative Model of Network Formation
• A class of games possessing pure-strategy Nash equilibria
• Accessing nearby copies of replicated objects in a distributed environment
• Algorithmic Game Theory
• Bounded budget betweenness centrality game for strategic network formations
• Bounded budget connection (BBC) games or how to make friends and influence people, on a budget
• Fast Construction of Nets in Low-Dimensional Metrics and Their Applications
• Finding nearest neighbors in growth-restricted metrics
• LAND: stretch \((1 + {\epsilon})\) locality-aware networks for DHTs
• Nearest neighbor queries in metric spaces
• On a network creation game
• Potential functions and the inefficiency of equilibria
• Potential games
• Social and economic networks.
• The Price of Stability for Network Design with Fair Cost Allocation
• The complexity of pure Nash equilibria

Cited in

(9)

• scientific article; zbMATH DE number 1665657 (Why is no real title available?)
• Self-organizing flows in social networks
• STRUCTURAL PROPERTIES OF CORE–PERIPHERY COMMUNITIES
• Interests diffusion in social networks
• Kinematics of network flow: forecasting the emergence of hotspots
• Information-sharing in social networks
• Self-organised criticality and emergent hyperbolic networks: blueprint for complexity in social dynamics
• Community structures in information networks for a discrete agent population
• Privacy-conscious information diffusion in social networks

This page was built for publication: Self-organizing flows in social networks

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