Category-based routing in social networks: membership dimension and the small-world phenomenon

DOI10.1016/J.TCS.2013.04.027zbMATH Open1278.91121arXiv1110.4499OpenAlexW2954747556MaRDI QIDQ386908FDOQ386908

Authors: Michael T. Goodrich, Maarten Löffler, Darren Strash, Lowell Trott, David Eppstein 

Publication date: 11 December 2013

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: A classic experiment by Milgram shows that individuals can route messages along short paths in social networks, given only simple categorical information about recipients (such as "he is a prominent lawyer in Boston" or "she is a Freshman sociology major at Harvard"). That is, these networks have very short paths between pairs of nodes (the so-called small-world phenomenon); moreover, participants are able to route messages along these paths even though each person is only aware of a small part of the network topology. Some sociologists conjecture that participants in such scenarios use a greedy routing strategy in which they forward messages to acquaintances that have more categories in common with the recipient than they do, and similar strategies have recently been proposed for routing messages in dynamic ad-hoc networks of mobile devices. In this paper, we introduce a network property called membership dimension, which characterizes the cognitive load required to maintain relationships between participants and categories in a social network. We show that any connected network has a system of categories that will support greedy routing, but that these categories can be made to have small membership dimension if and only if the underlying network exhibits the small-world phenomenon.

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

Recommendations

• A category-theoretic approach to social network analysis
• Small-world properties of Facebook group networks
• The Small Community Phenomenon in Networks: Models, Algorithms and Applications
• Social network coordination and graph routing
• The small-community phenomenon in networks
• A ``small world approach to heterogeneous networks
• Distributed routing in small-world networks
• Small Worlds as Navigable Augmented Networks: Model, Analysis, and Validation

zbMATH Keywords

social networkcategory routingmembership dimensionsmall world

Mathematics Subject Classification ID

Social networks; opinion dynamics (91D30) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Network design and communication in computer systems (68M10)

Cites Work

• Collective dynamics of `small-world' networks
• A general model of web graphs
• On a conjecture related to geometric routing
• Succinct Greedy Graph Drawing in the Hyperbolic Plane
• Succinct greedy geometric routing in the Euclidean plane
• Models of the small world.
• Routing with guaranteed delivery in ad hoc wireless networks
• Some results on greedy embeddings in metric spaces
• The small-world phenomenon: an algorithmic perspective
• Could any graph be turned into a small-world?
• Optimum binary search trees
• Geometric ad-hoc routing
• Biased Search Trees
• Analyzing Kleinberg's (and other) small-world models
• An Algorithm to Construct Greedy Drawings of Triangulations

Cited In (1)

• A study of how the Watts-Strogatz model relates to an economic system's utility

This page was built for publication: Category-based routing in social networks: membership dimension and the small-world phenomenon

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