## DIMACS TR: 99-35

## The Role Assignment Model Nearly Fits Most Social Networks

### Authors: Aleksandar Pekec and Fred S. Roberts

**
ABSTRACT
**

Role assignments, introduced by Everett and Borgatti \cite{Everett91},
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${\em -role assignment} is a surjective
function mapping each vertex into a positive integer $1,2,\ldots,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)\rightarrow\{1,\ldots, 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.

Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1999/99-35.ps.gz

DIMACS Home Page