Research Abstracts - 2007

The Problem

How do social networks grow from a seed of one or two nodes to create a larger entity having, say, 20 to 100 nodes? Pictorial representations are commonly used to show this process, but these do not make explicit the underlying key parameters. We propose a depiction based on two very simple parameters that reveal aspects of the evolution and dynamics of the evolution of small groups.

Motivation

Over the past ten years, there has been an accelerated interest in networks and graphical models for representing properties of complex systems, ranging from cellular or molecular organizations to interactions among people. Most of these studies have examined very large networks. In contrast, our focus is on small social groups such as militant cliques engaged in terrorism, or street gangs, as well as small, non-violent organizations such as educational initiatives or start-ups. The groups under study have less than 20 members that play active roles, although supporting membership can reach 50 or more.

Previous Work

Detailed studies of small groups that show various stages of the evolution of a group are surprisingly scarce. Whyte’s classic study (7) of “Cormerville” was completed in the ‘40’s. As yet, we have found no comparable study other than those being conducted by Atran, Sageman et al. on several terrorist militant core as part of a joint MURI project. One goal is to expand our small database to encompass a broad range of quite different small groups, both violent and non-violent. Fortunately, on the theoretical front there has been significant progress in understanding the evolution of cliques in random graphs, and small world and scale-free graphs. Parameters of interest include edge probability, percolation transitions that insure significant clustering, degree distributions, centrality measures, and several clustering parameters. (2,3,4,6.)

Approach

Consider the very simple case where a small group has evolved to only 12 active members. If we were to show this evolution pictorially, there would be 10¹¹ possible forms for the final 12 node network. For 18 final nodes, there would be 10³⁰ possibilities. Only a very trivial fraction of these forms fall into categories depicted in graph atlases (5). The implication is that pictorial representations are not the key to understanding small group evolution – there are too many possible forms. Hence the representation should focus on changes in some key parameters, such as the centrality measures proposed decades ago, or the more recent proposals of clustering, betweenness, etc. For our preliminary explorations, we have chosen Freeman’s 1970 measure of centrality (1) based on maximum degree, and a very simply form of clustering, based on the number of triangles in the network. The rationale is simple: effective small groups require both leadership and coherence, i.e. some measure of the bonding and trust within the group.

Result

Our measure of leadership, L, is based on the dominance of the node with the maximum degree with respect to the degrees of the other nodes; the bonding or coherence, C, in the network is measured by the number of triangles:

Coherence, C: #triangles / _nC₃

Leadership, L: Σ (MaxDeg - VtxDeg.) / (n-1)*(n-2)

where the (n-1)*(n-2) denominator for L normalizes the measure to 1, as does _nC₃ for C. Note that these parametric choices counterbalance one another: as coherence C increases, leadership decreases, as indicated by the compass in the left panel below. In both of these panels, we illustrate evolutionary paths, with the trajectories broken into several time steps. (Note difference in scales.) In the right panel, we also identify approximate regions for several common types of graphs. These regions become of greater interest in later stages of the group evolutionary process, such as when tight clusters are linked to create hierarchical, multiscale networks. (Leadership and clustering in these forms require different parameters for modeling.) Following more data collection, our next step is to model the evolutionary trajectories highlighted below.

References:

[1] Barabasi, A. L. & R. Albert. Emergence of scaling in random neworks. Science 286, 509-512, 1999.

[2] Freeman, L. C. Centrality in Social Networks. Social Networks 1, 215-239, 1978.

[3] Newman, M. E. J. Measure of betweenness centrality based on random walks. Social Networks 27, 39-54, 2005.

[4] Palla, G., Derenyi, I., Farkas, I. & T. Vicsek. Al Uncovering the overlapping community structure of complex networks in nature and society. Nature 435, 814-818, 2005.

[5] Read, R. C. & R. J. Wilson. An Atlas of Graphs. Oxford, 1998.

[6] Watts, D. J. & S. H. Strogatz. Collective dynamics of “small world” networks. Nature 393, 440-442, 1998.

[7] Whyte, W. F. Street Corner Society. Univ. of Chicago. 2nd Ed, 1955.

Supported by: AFOSR under contract #FA9550-05-1-0321