D. Zinoviev and V. Duong, "Massive Online Social Networks as Linear Spaces," poster presentation at Sunbelt XXIX Social Networks Conference, San Diego, CA, March 2009

Abstract

In this paper, we study the geometrical properties of massive online social networks (MOSN). A MOSN can be represented as a graph, where the nodes are network members and the edges are "friendship" relationships. The graph induces a metric space with the distance between any two nodes defined as the length of the shortest path in the graph connecting the nodes. Thus, one can argue about the distance between the nodes, but not about their positions in the MOSN.

The metric space can be embedded without distortion in an O(|N|)-dimensional linear space, where |N|>>1 is the number of nodes.  Because of the high dimensionality, this linear space has limited, if any, practical applicability. In particular, the coordinates cannot be used to define the "center" and the "periphery" of the MOSN.
We show how to construct an O(D)-dimensional subspace of the original linear space, where D<<|N| is the graph diameter. We further show that all coordinates in the subspace are approximately dependent, and thus the subspace is approximately one-dimensional. The new single coordinate d is the mean distance from a node to all other nodes in the MOSN. We use this coordinate to classify nodes as central, middle or peripheral, and demonstrate that at least in one MOSN - Odnoklassniki.ru - the coordinate d is socially significant: the average age of the MOSN members is a reasonably smooth function of d, with younger members being in the center and at the periphery, and older members being in the middle.