Qualiry and Quantity, 14 (1980) 101-116 101 0 Elsevier Scientific Publishing Company, Amsterdam - Printed in The Netherlands

APPLIED

NETWORK

ANALYSIS

KEES NIEMGLLER and BERT SCHIJF Institute for Political Science and Sociological Institute, University of Amsterdam, The Netherlands

Description and analysis of social relations is an important aspect of the social sciences. Such relations may be formal, as within or between organizations, or informal, The social units between which relations like friendships. can be defined may be individuals or collectivities, like families, corporations or nations. In the last 10 years an increasing number of social scientists from different disciplines have used network analysis or graph theory for the analysis and description of social relations. Applications of network analysis can be found in the work of anthropologists (Mitchell, 1969; Boissevain and Mitchell, 1973; Boissevain, 1973), social-psychological and sociometric reBavelas, 1968), research on the search (Moreno, 1951; structure of interlocking directorates (Fennema and Schijf, 1979), local influence relations (Laumann and Pappi, 1976), 1976) and the formation of groups cognitive maps (Axelrod, in the United Nations (Stokman, 1977a). This list is not exhaustive but suggests how many and how diverse the applications are. Indeed, the popularity of network analysis can be inferred from the founding in 1978 of a special journal for this sort of analysis, Social Networks, and an organization, the International Network for Social Network Analysis, which publishes a newsletter called Connections. There are also a growing number of articles and special issues of journals about topics in network analysis (Journal of Mathematical Sociology, vol. 5, no. 1, 1977) and Sociological Methods and 7, November 1978). A bibliography of studResearch, vol. ies on social networks has been published by Freeman (1976).

102

Some Graph-theoretical Concepts

Graph theory is a branch of mathematics which studies the properties of configurations of points and lines. This section discusses only those of its concepts mentioned in the rest of this chapter. The reader is referred to general introductions like Harary et al. (1965), Harary (1972), Berge (1962) and Doreian (1970) for further information and references. A well-known problem of graph theory is the terminology. Points are sometimes called vertices or nodes, while the lines have names like edges or arcs. This is also the case with the terms network and graph. A graph is defined as a set of points and a set of lines connecting pairs of points. According to the definition of Harary et al. (1965, p. 408), a network is a graph whose lines have a value assigned to them. In many articles on network analysis this distinction is not made and we will do the same in this chapter. An example of a graph can be seen in Figure 1. This graph consists of four points and two lines. Point p4 is a member of the set of points but has no connections with other points. It is "isolated". When two points are directly connected by a line they are "adjacent". Given a pair of points, one point is "reachable" from the other if and only if between them there is a "path" or sequence of

Fig. 1. A graph of four points. p2

Pl

&A

P3

Fig. 2. A graph of two components.

PL Ip5

103 In Figure 1 there is a path between p1 points and lines. and p3 because there are the two lines between pl and p3 and between p2 and p3. When every point is reachable from any Subsets other points the (sub)graph is called "connected". of connected points in a network are called "components". The Figure 2 shows a graph consisting of two components. "distance" between points is the length of the shortest path between these points. For example, the distance between pl and p3 is two in Figure 1, but one in Figure 2. The "diameter" of a graph is the longest distance in that graph. Notwithstanding the simplicity of our conceptual equipwe are now able to distinguish several kinds of ment so far, graphs. "Directed" or "undirected" graphs. In a directed 1) lines have a direcgraph or simple "digraph" , all tion (arcs), whereas in an undirected graph the lines have no direction (edges). "Multigraphs". A graph represents just one rela2) tion. This does not mean that parallel lines are impossible. Each time a relation occurs between two elements we can draw a line between the corresponding points. For example, if pl and p2 represent two corporations, and a line between those two points means "there is a person who has positions in both corporations", the graph in Figure 3(a) represents the situation wherein one person has functions in both corporations, while Figure 3(b) illustrates the situation where three persons have positions in pl

(b)

(a) ?

0

Q P2

Fig. 3. A graph with (a) single and (b) multiple lines.

Fig. 4. A complete graph.

q-p3

104

3)

4)

5)

A graph with one or more such multias well as p2. ple lines is called a "multigraph". Not all authors sometimes a multigraph is deagree on this point: fined as a graph representing more than one type of relation. "Valued" graphs. A valued graph is a graph with values assigned to the lines. Such values make it possible to differentiate among the relation between pairs of points. When we compare the graphs in "Complete" graphs. the difference is striking. Figure 1 and Figure 4, In the first graph only a few relations are present while in the second one all possible connections are Such a graph is called a "complete" graph present. and is formally defined as a graph in which every pair of points is adjacent. Such graphs are also called "cliques". "Signed" graphs. A signed graph is obtained by designating each line of the graph as positive or negative. This type of graph enables us to analyze dichotomous relationships like love and hate or friendship and animosity. This is useful in balance theory (Harary et al., 1965, Chapter 13).

Applied Network Analysis

Burt (1978a) has recently pointed out that there exists a disconcerting separation between the theoretical and mathematical treatment of network analysis and graph theory and the substantive use of network and graph-theoretical conHe therefore believes that there is a need for cepts. methodology for applying ab"applied network analysis" stract models of network structures in substantive, empirical research. The application of graph theoretical concepts in social research has a fairly long history, starting with the sociometric research of Moreno (1934). However, the use of many concepts has been loose and imprecise. In many concepts have the status anthropology, for instance, only of metaphors without any graph-theoretical basis for a On the other hand, many emcritique (see Barnes, 1969). pirical studies inspired the development of graph-theoretical concepts, while those concepts are tested again in emVarious point centrality indices and pirical research. many clique concepts are examples of this relationship between empirical research and network analysis.

105 To give an overview of the enormous flow of recent litwe make use of the six erature on applied network analysis, As we modes of network analysis, proposed by Burt (1978a). a graph consists of points and lines. For the have seen, the points, we can distinguish three levels of aggregation: individual points, subsets of points and the whole set of points in the graph. For each of the levels of aggregation we can distinguish two approaches, the positional or attributional approach on the one hand and the relational approach on the other. The relational approach focuses on the relations points have in the network. At one level, individuals indicate how they use their relations with other persons to get things done or to communicate with each other. At the level of subgroups, the focus is often on cohesiveness within subsets of points and on the relations between different subsets. Methods to characterize the structure of the network as a whole from the existence of certain types of relations is a point of focus at the highest level of aggregation. In the positional or attributional approach the emphasis is on positions in the network. Certain attributes or status are ascribed to points, depending on their positions. At the individual level, there are point centrality indices to investigate the positions of points in a network. The positional approach to the analysis of subgroups within a network consists of locating and comparing jointly-occupied positions for sets of structurally equivalent points. For instance, points with the same mean distance to all other points might be seen as group of points with a common structural position. At the level of the network as a whole, the focus is on relations among positions in the network. The approach at this level overlaps the positional approach to subgroups and has been developed by the same researchers, We will therefore not discuss it separately. Although we can distinguish six possible modes of network analysis this does not mean that all modes represent equal amounts of research at present. Studies on the individual positional approach are far more extensive than on the individual relational approach, as can be seen in the many articles on point centrality indices. The same holds for the relational subgroup approach compared to the positional subgroup approach. The amount of articles on clique detection methods is enormous (Meeusen and Cuyvers, 1978). The two dimensional classification results in six categories as represented in Table 1. In the rest of the chapter, five of the six are discussed more extensively.

106 TABLE Modes

1 of Network

Analysis Focus Individual

Subcets

Approach

points

points

of points

Relational

individual

subgroup

relational

relational

relational

networks

approach

approach

individual positional

subgroup positional

approach

approach

Positional

Individual

relational

of

Whole

set

positional networks

approach

This approach is characterized by its focus on the relations between the individual points in a network. Of key interest are the kind of relations, the number of relations and the way they are used. AS the emphasis is on the socalled "personal network" of individuals, this approach is prominent in sociometric research and anthropology. It reflects mostly research on networks within small groups. Persons are usually invited to say whether or not they have certain relations (e.g., kinship, friendship) with others. These are not always easy questions to answer for the respondents because people make poor estimates of the number of their own acquaintances (Killworth and Bernard, 1976). Methods have been developed for studying personal networks by mass survey (McCallister and Fischer, 1978). The use of graph-theoretical concepts in social science started with this approach. It was the psychologist Moreno (1934) who collected data on preferential relations in a group and used this information to draw a so-called "sociogram". He then used this sociogram to investigate the network of preferential relations among members of the group. This kind of research was extended by Festinger (1949), Forsyth and Katz (1946) and Bavelas (1950, 1968) among others. It was Bavelas who introduced a centrality index for indi-

107 vidual members of the group. By the summation of these individual indices he constructed a measure for the cohesion That means that Bavelas used both the indiof the group. vidual relational and also the positional approach, though fairly crudely. In anthropological research attention has been paid to the networks constructed by "friends of friends" (BoissePeople use those networks to get things done, vain, 1973). Still, although the relations differ widely in intensity. the less intense relations are very useful, as Granovetter (1973) points out. He distinguishes two types of relations: weak or extensive relations and strong or intensive relations. His research suggests that weak ties rather than strong ties are used for obtaining new information. In a group of individuals with strong relations everybody has about the same information because new information will be passed among the members very fast. People have to break out of their own strongly-related group, using their weak relations with other groups for getting new information, especially if the members of the other group have a different social position (see also Liu and Duff, 1972). A last group of studies to mention in this area are experiments on the difficulty or ease of finding contact chains. These experiments deal with "the small world problem". Sometimes a surprisingly small number of contacts are needed for a person to send a message across the United States to somebody he does not know. But in many cases the experiment failed completely (Milgram, 1967; Travers and Milgram, 1969; Korte and Milgram, 1970; Killworth and Bernard, 1978). Relational

subgroups

in

the

network

A different way to investigate the structure of a network is to locate highly connected subgroups and then analyze the and/or intra-subgroup relations. interThis kind of research on the cohesiveness of subgroups is common. There is empirical research on groups in a kinship network, intense friendship groups, elite studies and studies of financial groups in networks of interlocking directorates. Many of those empirical studies have been the basis for research on the graph-theoretical concept of a clique, though less severely-defined concepts like social circles and k-plexes are proposed. There is also some research on indices for overlapping membership between different groups (Bonacich, 1972; Bonacich, 1978).

108 A basic graph-theoretical problem is how the intensity of the relations within a group can be formalized. The most popular concept is that of a clique, defined as a maximal complete subgraph. (The graph in Figure 4 is such a clique.) This definition, introduced by Lute and Perry (1949), has the drawback of being highly restrictive, requiring that all points in the clique be directly connected to each other. Use of this definition of a clique would quite often miss interesting social groups which are densely but not fully connected. The idea of a clique has been extended in several ways. Lute (1950) introduced the concept of an "n-clique" defined as a maximal subgraph with a maximal distance between the points of n. This definition of the structure of a clique is less restrictive because indirect relations of various length are now allowed and these indirect relations are not bounded by the clique itself. This n-clique concept was modified and further developed by Alba (1973) and recently by Mokken (1979) who introduced three related concepts, clubs and clans, cliques, depending on restrictions on the diameter of the subgraph. With the introduction of less restricted clique concepts another problem arose. For a long time it was impossible to detect all the cliques even in a network of moderate size. This problem of capacity has been solved to a large extent by new generations of high-speed computers and the development of efficient clique-finding algorithms (Bron and Kerbosch, 1973; Alt and Schofield, 1978), though these algorithms do not suit all definitions of cliques. Alba and Kadushin (1976) introduce the idea of social circles. A circle is a group where the integration of the membership occurs through short chains of connection rather than face-to-face contact. This intuitive definition lies somewhere between the more restricted concepts of n-cliques and components. Alba and Moore (1978) operationalize the idea of a social circle by joining overlapping cliques. By doing this they get a cluster of partly overlapping cliques which forms a highly-connected group of individuals. One potential application of this operationalized concept of a social circle is to social networks which have central and peripheral regions. A central region is one in which connections are relatively dense among the members of the group. In peripheral regions, connections are often sparse among the members, while their important links are usually those which lead to the center.

109 A second way to extend the concept of a clique has been They introproposed by Doreian (1969) and Peay (1974). duce a stepwise clique detection algorithm for valued The location of cliques starts without taking graphs. In the next step the into account the value of the lines. lines with lowest value are deleted and the clique detecThis goes on till the cliques formed by tion is repeated. This lines with highest value are the only ones left. procedure gives an insight into the "tightness" of the different cliques but is very restrictive because it takes only maximal complete subgraphs into account. A generalization to n-cliques is possible. An analogous procedure has been proposed for components, the so-called analysis of "nested components" (Stokman, 1977a). The idea of nested components has been applied in research on legislative behavior (Stokman, 1977a) and in research on interlocking directorates (Fennema and Schijf, 1979). In the latter case the number of interlocking directorates between two corporations is assigned to the lines of the network of interlocking directorates. A third extension of the clique concept has recently been proposed by Seidman and Foster (1978). They mention three properties of clique-like structures. The first is the degree to which a short path is present from each point to every other point in the subgraph. The second property is the "robustness" of the structure, the degree to which the structure is vulnerable to the removal of any given individual point. The robustness of individual cliques, in turn, is closely related to the stability of the clique structure of the network as a whole. The third property of clique-like structures is the degree to which such structures are tied into the total network. The k-plex structure which Seidman and Foster finally propose is defined as a clique with n points in which each point is connected with at least n - k of the other points. Thus instead of extending the distances in the clique they lessen the number of lines in the clique. Research on groups is at the border between groups in the network and the network as a whole. There is interest not only in the cohesiveness of groups but also in the connections between different groups. The existence of a group, particularly one centrally located in the network and possessing a broad membership, is evidence that a network is integrated. On the other hand, the absence of such a central group or the existence of many small ones,

110 widely dispersed and with narrowly-defined very few inter-subgroup relations, shows fragmented system. Relational

memberships with a (more or less)

networks

At the level of the network as a whole, several types of research in the relational approach can be distinguished, First, there are many formalizations of the idea of the "compactness" of a network, sometimes called graph centrality. Many indices are based on the position of individual points in the network. Some of these will be discussed in the next section. A general discussion of these graph centrality measures can be found in Freeman (1979). Second, since the research of Heider (1946) on attitudinal structures, many extensions of so-called "balance theory" have been proposed. In this research, the concept of the signed graph is used to indicate positive and negative relations in a group of individuals. Generalizations are concerned with the stability of networks of, for instance, social relations (Davis, 1976; Cartwright and Harary, 1970) or cognitive maps of decision makers (Axelrod, 1976). The most formal and general formulation of balance theory is proposed by Katai and Insuke (1978). Finally, research has been done on statistical tests for specific hypotheses of structural trends in networks. These tests are developed by Holland and Leinhardt (1970, 1976, 1978). In their work, they try to bridge the gap between certain properties at the local level and properties for the network as a whole. They do this by examining local relational properties and then determining whether they hold, on average, across the total network. Their test is restricted to directed graphs where the property of "transitivity" for all possible triads is investigated. Between two given points in a directed graph there can exist one of the three following situations: (1) there is no connection at all, (2) there is only one line (arc) in one direction and (3) there are two lines (arcs), in both directions. The second situation is called "asymmetric", while the third is called "mutual". Each possible triad can now be characterized by the frequency of each of the three situations. There are 16 possible types of triads. The frequencies of the types of triads in the network are summarized in a triad census T, which is a vector with 16 elements given by T = (Tl, T2, . . . . Ti, . . . . Tl6), where Ti

111 denotes the number of traids of type i. Because a triad census T is a summation over all possible subgraphs of three elements, the information in T is relatively stable and is not significantly affected by a few changes in the number or direction of lines in the directed graph. A test statistic based on T has been developed to test the overall structure of a network against the predictions of the random digraph distribution (Holland and Leinhardt, 1978). Individual

positional

approach

Most applied network analysis research to date is in this approach. In many empirical studies from Bavelas (1950, 1968) on, the focus is on the central positions points can have in network. This focus is common in sociometric research but also in the many studies on interlocking directorates, where again and again financial institutions are in the most central positions. We can distinguish three bases for indices: indices based on number of adjacencies, indices based on "betweenness", and indices based on "closeness". A general overview of indices can be found in Freeman (1979), while Hdivik and Gleditsch (1970) have tried to formalize several parameters in a graph. The simplest conception of point centrality is based on the number of points a given point is adjacent to, sometimes called "degree" or "adjacency". Although many authors (see Freeman, 1979) have developed indices based on this concept, only Nieminen (1974) has introduced a simple and general measure, which is the degree itself and thus indicates the number of points a given point is directly connected to. The magnitude of this index is partly a function of the size of the network. It might be desirable to have a measure independent of the size of the network. The index can therefore be standardized by dividing the index by n - 1, being the maximum number of points to which a given point could be adjacent in a network of n points. More refined indices of point centrality are based on the idea of "betweenness". This idea is illustrated in Figure 1, where only point p2 lies on a path between another pair Indices based on betweenness are useful to (PI and ~3). indicate the potential of a point for control over communication in a network. Direct measures were developed by Anthonisse (1971) and Freeman (1977). A third group of indices is based on the idea of "close-

112 ness" of a given point to all other points in the network (Bavelas, 1950, 1968; Beauchamp, 1965). For instance, the mean distance of a given point to all others is such an These indices can be called "global" because they index. take the connections of all the points in a network into account, while "local" indices take only direct relations The simplest of these global indices is into account. Sabidussi's (1966). His index measures the centrality of a point by summing the distances t:, all other points. (Acthis is an inverse cent~.tlity index since it intually, creases as a given point has longer distances to other points.) The positional

approach

to

groups

and networks

The focus here is on locating groups of points which are structurally equivalent in relation to all other points. Points in such groups are structurally equivalent to the extent that they have identical positions in the network. Research on this approach is centered around White and his co-workers (White et al., 1976; Boorman and White, 1976; Arabie, Boorman and Levitt, 1978). Breiger et al., 1975; Techniques to locate structurally equivalent groups are based on the idea of "block models". Block models are, so to speak, the opposite of cliques. In clique research, the emphasis is on cohesiveness among the members of the clique, while in a block model the emphasis is on the similarity of positions points have in relation to the other points in the network. The outcomes of the two different analyses are not necessarily the same. Burt has recently compared these two approaches (Burt, 1978b). In other approaches usually only one type of relation is taken into account. In block models various types of relations can be analyzed at the same time, including for instance relations of "liking" and "disliking" (Breiger, 1974). Each type of relation is represented in a square matrix with a row and the corresponding column of the matrix assigned to each point in the network. So the fundamental data structure generally takes the n-way form of k square matrices, where k is the number of relations considered. Block modelling begins with partitioning the points in the network in sets of structurally equivalent points or "blocks". In each matrix the rows and columns are arranged so that the members of a block are grouped together.

113 Attention focuses particularly on blocks which have no, or of relations: these blocks are called very few, instances "zero blocks". Two computer programs for block models have CONCOR is a hierarchibeen developed, CONCOR and BLOCKER. cal clustering algorithm where raw data are rearranged to form blocks (for severe critiques of this program see Schwartz, 1977, and Kappelhoff, 1978). BLOCKER on the other hand relates to a particular block model hypothesis. One has to specify for each matrix what the zero blocks will be when some common partition on the points of the network is imposed on all the matrices. Substantive judgements are required in both situations. In CONCOR one must decide when to stop further splitting of blocks; in BLOCKER one must indicate which block models constitute appropriate hypotheses. The block model approach relates to rather small usually of the common sociometric type. groups of points, Breiger (1979) applies this approach to community elite structures.

Future Developments This chapter gives an overview of recent trends in applied network analysis. The purpose of such a global view is to give the interested reader a start for a further snowball-sampling of the literature of interest. Given the increase in publications on network analysis and graph theory and its applications, it must be feared that a host of new concepts and methodological techniques will arise. Together with the already existing semantic chaos, it will not be easy to stay well informed. On the other hand more and more authors are convinced of the necessity to generalize concepts and indices, like the work of Hplivik and Gleditch (1970) concerning the classification of centrality measures, the formalization of clique concepts and the generalization of balance theory. It seems reasonable to expect a further growth in this direction. Another topic will be the "statistical" side of network analysis, where problems include sampling from a graph, the distribution functions of indices, and stochastic graphs. All these problems are presently receiving attention. For further information, see Bloemena (1964), Frank (1971), Tapiero, Capobianco and Lewin (1975), Granovetter (1976) and Frank (1978). Another problem is the static nature of network analysis techniques; To deal with changing structures

114 over time dynamic network analysis techniques are needed. Although there is some overlap between network analysis and cluster analysis (see Bock, 1974), not many authors have paid attention to the relationship between network analysis and other models of data analysis. Examples include Laumann and Pappi (1976) who combined their network analysis with multidimensional scaling and Stokman (1977a, 1977b) who combined it with stochastic cumulative scaling. In the field of applications the possibilities are bounded only by our imagination. However, with the growing complexity and formalization of graph-.theoretical concepts and methodological techniques, and the increasing size of the networks investigated, the developments of fast algorithms and useroriented computer programs may be of decisive importance for future applications of network analysis.

References Alba, Alba,

R.D. and Kadushin, C. (1976). ‘The intersection of social circles. A new measure of social proximity in networks’, SociologicalMethods & Research 5: 77-103. R.D. (1973). ‘A graph-theoretic definition of sociometric clique’, Joumal of Mathematical

Sociology 3: 113-l 26. Alba, R.D. and Moore, G. (1978). ‘Elite social circles’, SociologicalMethods & Research 7: 167-I 88. Alt, J. and Schofield, N. (1978). ‘Clique Analysis of a tolerance relation’, Joumalof Mathematical Sociology 6: 155-162. Anthonisse, J.M. (1971). The rush in a directed graph. Amsterdam: Mathematical Centre. Arabie, P., Boorman, S.A. and Levitt, P.R. (1978). ‘Constructing block-models: How and why’, Journal of ~1athematicalPs~~cl~olog.y 17: 21-63. Axelrod, R. (ed.) (1976). Structure ofDecision. The Cogrlitive Maps of PoliticalElites. Princeton. N.J.: Rinceton University Press. Barnes, J.A. (1969). ‘Graph theory and social networks: a technical comment on connectedness and connectivity‘,Sociologjj 3: 215-232. Bavelss, A. (1950, 1968). ‘Communication patterns in tabk-oriented groups’. in Cartwright, D. and Zander, A. (eds.) Group Dymnzics: Research and Theory. London: Tavistock. Beauchamp, M.A. (1965). ‘An improved index of cefltrality’, BehaGoralScience 10: 161.163. Berge, C. (1962). The Theory of’Graphs arid Its Applications. London: Methuen. Bloemena, A.R. (1964). Sampling from a graph. Amsterdam: Mathematical Centre. Bock, H.H. (1974).Autonnatische Klassifikafiorz. Gbttingen: Vandenhoeck. Boissevain, J. and Mitchell, J.C. teds.) (1973). NetworkAnalysis. Studies in Humm Interaction. Den Haag: Mouton. Boissevain, J. (1973). Friends of Friends. Netwurhx, Manipulators and Coalitions. Oxford: Basil Blackwell. Bonacich, P. (1972). ‘Technique for analyzing overlapping memberships’, in Costner, H.L. (ed.) Sociological Methodology. San, Francisco: Jossey-Bass Inc. Bonacich, P. (1978). ‘Using Boolean algebra to analyze overlapping mernbcrships’, in Schuessler, K.1’. (ed.) SociologicalMethodology. San Francisco: Jossey-Bass Inc. Boorman, S.A. and White, H.C. (1976). ‘Social structure from multiple networks: 11, role structures’, American Journalof Sociology 81 : 1384-1446. Brciger, R.L. (1974). The duality of perconsand groups’,SociuIEbrees 53: 181-190.

115

Breiger, R.L., Boorman, S.A. and Arabie, P. (1975). ‘An algorithm for clustering relational data with applications to social network analysis and comparison with multidimensional scaling’, Journal ofMathematicalPsychology

12: 328-382.

Breiger, R.L. (1979). ‘Toward an operational theory of community elite structures’, Quality and Quantity 13: 21-57. Bron, C. and Kerbosch, J. (1973). ‘Finding all cliques of an undirected graph’, Communications of the ACM 16: 575-517. Burt, R.S. (1976). ‘Positions in networks’,SocialForces 55: 93-122. Burt, R.S. (1978a). ‘Applied network analysis: An overview’, Sociological Methods &Research 7: 123-131. Burt, R.S. (1978b). ‘Cohesion versus structural equivalence as basis for network subgroups’, Sociological Methods and Research 7: 189-2 13. Cartwright, D. and Harary, F. (1970). ‘Ambivalence and indifference in generalizations of structural balance’, Behavioral Science 15: 497-5 13. Davis, J.A. (1967). ‘Clustering and structural balance ingraphs’, Human Relations 20: 181-187. Doreian, P. (1969). ‘A note on the detection of cliques in valued graphs’,Sociometry 32: 237-242. Doreian, P. (1970). Mathematics and the Study of Social Relations. London: Weidenfeld and Nicolson. Fennema, M. and Schijf, H. (1979). ‘Analyzing interlocking directorates: theory and method’, Social Networks 1: 297-332. Festinger, L. (1949). ‘The analysis of sociograms using matrix algebra’, Human Relafions 2: 153-158. Forsyth, E. and Katz, L. (1946). ‘A matrix approach to the analysis of sociometric data: preliminary report’, Sociometry 9: 340-347. Frank, 0. (197 1). Statistical Inference in Graphs. Stockholm: Research Institute of National Defense. Frank, 0. (1978). ‘Sampling and estimation in large socialnetworks’,SocialNetworks 1: 91-101. Freeman, L.C. (1976). A Bibliography of Social Networks, Monticello: Council of Planning Librarians. Freeman, L.C. (1977). ‘A set of measures of centrality based on betweenness’, Sociometry 40: 35-41. Freeman, L.C. (1979). ‘Centrality in social networks’,SocialNetworks 1: 215-241. Granovetter, M.S. (1973). ‘The strength of weak ties’,American Journal of Sociology 78: 1360-1379. Granovetter, M.S. (1976). ‘Network sampling: some first steps’, American Journal of Sociology 81: 1287-1303. Harary, F., Norman, R.Z. and Cartwright, D. (1965). Sfructural Models: An Introduction to the Theory of Directed Graphs. New York: Wiley. Harary, F. (1972). Graph theory. Reading: Addison-Wesley Publishing Company. Heider, F. (1946). ‘Attitudes and cognitive organization’, Journal of Psychology 21: 107-l 12. Hdivik, T. and Gleditsch (1970). ‘Structural parameters of graphs: A theoretical investigation’, Quality

and Quantity

4: 193-209.

Holland, P.W. and Ieinhardt,

S. (1970). ‘A method for detecting structure in sociometric data’, 76: 492-5 13. Holland, P.W. and Leinhardt, S. (1976). ‘Local structure in social networks’, in Heise, D. (ed.) Sociological Methodology. San Francisco: Jossey-Bass. Holland, P.W. and Leinhardt, S. (1978). ‘An omnibus test for social structure using triads’, Sociological American

Methods

Journal

of Sociology

and Research

7: 227-256.

Hubbell, C. (1965). ‘An input-output approach to clique identification’,Sociometry 28: 377-399. Kappelhoff, P. (1978). ‘Structuranalyse socialer Netzwerke mit Hilfe von Blockmodellen’, Format 2: 2981. Katai, 0. and Sousuke, I. (1978). ‘Studies on the balancing, the minimal balancing and the minimum balancing process for social groups with planar and nonplanar graph structures’, Journal of Mathematical Psychology 18: 140-176. Killworth, P. and Bernard, H.R. (1976). ‘Information accuracy in social network data’, Human Organization

35: 267-286.

Killworth, P. and Bernard, H.R. (1978). ‘The reverse small-world experiment’,Social 159-193.

Networks

1:

116 Korte,

C. and Milgram, S. (1970). ‘Acquaintanceship networks between racial groups: application of the small world method’, Journal ofPersonality and SocialPsychology 15: 101-108. Laumann, E.O. and Pappi, F.U. (1976). Networks of Collective Acrions. A Perspective on Community Influence Systems. New York: Academic Press. Liu, W.T. and Duff, R.W. (1972). ‘The strength in weak tics’, Public Opinion Quarterly 36: 361-366. Lute, R.D. and Perry, A. (1949). ‘A method of matrix analysis of group structure’, Psychometriko 14: 94-l 16. Lute, R.D. (1950). ‘Connectivity and generalized cliques in sociometric group structure’, Psychometriku 15: 169-190. McCalIister, L. and Fischer, C.S. (1978). ‘A procedure for surveying personal networks’, Sociological MethodsandResearch I: 131-148. Meeusen, W. and L. Cuyvers (1978). An annotated bibliography of clique detection algorithms and related graph theoretical problems. Paper prepared for the ECPR Conference, Grenoble April 6-12, 1978. Milgram, S. (1967). ‘The small world problem’,Psychology Todqv 22: 61-67. Mitchell, J.C. (ed.) (1969). SocialNetworks in Urban Situa0ons. Analysis ofPersona Relationships in Central African Towrzs. Manchester: Manchester University Press. Mokken, R.J. (1979). ‘Cliques, clubs and clans’, Quality and Quantity 13: 161-175. Moreno, J.L. (1934). Who shall survive? Washington D.C.: Nervous and Mental Diseas Publishing Co Moreno, J.L. (195 1). Sociornerry. Experimerztal Method and the Science of Society. New York: Beacon House. Nieminen, J. (1974). ‘On centrality in a graph’, Scandinavian Journalof Psvchology 15: 322-336. Peay, E. (1974). ‘Hierarchical clique structures’,Sociornetry 34: 54-65. Sabidussy, G. (1966). ‘The centrality index of a graph’,Psychometriku 31: 581-603. Sailer, L.D. (1978). ‘Structural equivalence: meaning and definition computation and application’, Social Networks 1: 7 3-9 1. Schwartz, J.E. (1977). ‘An examination of CONCOR and related methods for blocking sociometric data’, in Heise, D.R. (ed.) Sociological Methodology. San Francisco: Jossey-Bass Inc. Seidman, S.B. and Foster, B.L. (1978). ‘A graph-theoretic generalization of the clique concept’, Journal of MathermzticalSociology 6: 139-154. Stokman, F.N. (1977a). Roll Calls and Sponsorship: A MethodologicalAnalysis of Third World Group Formation in Ihe United Nations. Leiden: Sijthoff. Stokman, F.N. (1977b). ‘Grafentheoretische uitwerking van cumulative schaaltechnieken’,Methode?z en Data nieuwsbrief van de sociaal wetenschappelijke sectie van de VVS 2: 52-65. Tapiro, C., Capobianco, M.F. and Lewin, A.Y. (1975). ‘Structural inference in organizations’, Journal of Mathematical Sociology 4: 12 l-l 30. Travers, J. and MiIgram, S. (1969). ‘An experimental study of the small world problem’, Sociomerrv 32: 425-443. White, H.C., Boorman, S.A. and Breiger, R.L. (1976). ‘Social structure from multiple networh: I. Blockmodels of roles and positions’, American Journal of Sociology 81: 730-780.