The role assignment model nearly fits most social networks

Aleksandar Pekeč, Fred S. Roberts

Research output: Contribution to journalArticlepeer-review

14 Scopus citations

Abstract

Role assignments, introduced by Everett and Borgatti [Mathematical Social Sciences 26 (1991) 183], who called them role colorings, formalize the idea, arising in the theory of social networks, that individuals of the same social role will relate in the same way to individuals playing counterpart roles. If G is a graph, a k-role assignment is a surjective function mapping each vertex into a positive integer 1,2,...,k, so that if x and y have the same role, then the sets of roles assigned to their neighbors are the same. We show that all graphs G having no astronomical discrepancies between the minimum and the maximum degree have a k-role assignment. Furthermore, we introduce and study a natural measure expressing how close an onto map f:V(G)→{1,...,k} is to being a k-role assignment of a graph G=(V,E), and show that almost all graphs nearly have a k-role assignment.

Original languageEnglish (US)
Pages (from-to)275-293
Number of pages19
JournalMathematical social sciences
Volume41
Issue number3
DOIs
StatePublished - May 2001

All Science Journal Classification (ASJC) codes

  • Sociology and Political Science
  • Social Sciences(all)
  • Psychology(all)
  • Statistics, Probability and Uncertainty

Keywords

  • C60
  • C78
  • Role assignment
  • Role coloring
  • Social networks
  • Social role

Fingerprint Dive into the research topics of 'The role assignment model nearly fits most social networks'. Together they form a unique fingerprint.

Cite this