Determining groups from the clique structure in large social networks

Abstract

Ethnographers have traditionally defined human groups as disjoint collections of individuals who are linked to each other by regular interaction, shared perceptions and affective ties. They are internally differentiated: some members occupy a central position in the group, others are on the periphery or somewhere in between. This way of characterising a group is intuitive to seasoned observers but social network analysts seek a more systematic method for determining groups.

Freeman [Freeman, L.C., 1996. Cliques, Galois lattices, and the structure of human social groups, Social Networks 18, 173–187.] describes a formal model based on the concept of overlapping social network cliques. Freeman's analysis produces results that are consistent with ethnographic results but his technique is not easily implemented for very large data sets. This paper describes two algorithms based on Freeman's clique–lattice analysis. The first implements his technique exactly; the second is a modification that exploits the clique structure, thereby enabling the analysis of large complex networks. We apply both algorithms to a real data set and compare the results.

Introduction

In any human organisation in which individuals interact with each other on a daily basis, groups emerge quite naturally and often deliberately. The group structure in a network gives us new insight into the dynamics of the organisation. In particular, it helps us understand how information spreads throughout the organisation. This interest in group structure was motivated by its applications to information diffusion through a social network Rapoport, 1953a, Rapoport, 1953b, Erbe, 1962, Weenig, 1993, Yamaguchi, 1994, Frank, 1996, Buskens, 1998. Our particular interest is in modelling the rate and accuracy of the transmission of information in a stratified population (Bartholomew, 1982, chapter 9).

Ethnographers have traditionally defined human groups as collections of individuals with little or no overlap, linked to each other by regular interaction. Within such groups, members are aware of the existence of the group, they develop shared perceptions and affective ties, and each occupies a particular position in the group: at the core, on the periphery or somewhere in between. An individual is likely to be a member of several groups associated with particular contexts that might be defined for a particular time frame (Freeman, 1992). However, if the groups are well defined in terms of context there should be very little overlap between groups.

The ethnographic description of a group is based on intuitive ideas and does not help us determine how to systematically partition a network into meaningful subnetworks with as little human intervention as possible. As a result, social network researchers have made many attempts to formalise the group concept Frank, 1995, Flache and Macy, 1997, Zeggelink et al., 1997. One definition considers the concept of a clique, which is defined as a maximal subnetwork containing three or more actors all of whom are connected to each other. However, cliques are typically too small to satisfy the properties of an ethnographic group. In addition, an individual may belong to many different cliques, making the segmentation into subnetworks an almost impossible task.

Friedell (1967) introduced the concept of using semilattices to model complex organisational structure. Freeman (1996) extended this concept to Galois lattices to show that the underlying group structure in a social network is revealed in the overlapping patterns of cliques. He demonstrates his technique on two classical data sets and shows that the group composition he obtains using his formal method matches the group structure observed by the ethnographers. Freeman's technique enables a determination of the structure from a representation of the clique lattice. In the case of small networks (of the order of 20 cliques), this is often possible by visual inspection of the lattice but it is not feasible for very large data sets. In his original examples, the data sets consisted of less than 20 actors while the social network we study is at least five times this size. Two algorithms were developed to interpret the information in a formal description of the latticial representation of larger data sets rather than rely on visual interpretation. The first algorithm is an implementation of Freeman's technique. The second is a modification arising out of attempts at solving problems arising when the former was applied to a large complex network. The modified algorithm exploits a property of clique lattices in which the overlap pattern in the lower layers of the lattice mirrors the group structure. Both techniques are described in the following section. Resulting group structures are compared in the final section.