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

DOI10.1016/J.TCS.2013.04.027MaRDI QIDQ386908zbMATH OpenOpenAlexFDO

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)

Full work available at URL https://arxiv.org/abs/1110.4499, http://www.escholarship.org/uc/item/8760h7bj

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)

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.

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

Cites work

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

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)