Resilience of Small Social Networks

Abstract

The ability of a network to retain one or more specifed properties under perturbation of its structure is referred to as resilience. In this thesis, we focus on the resilience of small social networks and give primacy to the properties of connectedness and symmetry.

Many social networks rely on connectedness in order to function. Therefore, connectivity provides a suitable first measure of resilience. For connected networks with a single type of relationship (edge) between individuals (vertices), we measure edge (resp. vertex) resilience by the minimum number of edges (resp. vertices) that must be removed in order to disconnect it. We utilize Menger's Theorem to devise algorithms for determining the key individuals and relationships whose removal will disconnect the network.

A different notion of resilience is associated with network symmetry. In a symmetric network, there exists a set of vertices such that a permutation of the vertices leaves the network invariant. Symmetric networks are associated with redundancy (i.e., structural equivalence), implying that they can still function when some of the vertices/edges are removed. Most social networks are asymmetric; thus, a network's proximity to a symmetric network provides a useful measure of resilience. We introduce a blockmodeling strategy to determine the extent of structural equivalence within a network, thereby identifying symmetric subnetworks.

In the more complex situation where vertices are connected by multiple types of ties, the focus becomes the structure of compound relationships between individuals. We describe this multirelational structure as a partially ordered semigroup, represented by its Hasse diagram. We discuss qualitative differences between networks with connected and disconnected Hasse diagrams. The minimum number of edge/vertex changes required to disconnect a network's Hasse diagram is a useful notion of resilience of the relationship structure. We present algorithms for constructing Hasse diagrams and determining their associated resilience.

We apply the resilience formulations to study this phenomenon empirically for a variety of real-world networks. In particular, we investigate: (i) marriage and business relationships among medieval Florentine families; (ii) contact relationships among the covert network of 9/11 hijackers; and (iii) relational structure of love and power relations among members of a diverse set of urban communes in the United States in the 1970s.