Fundamentals of Social Network Analysis



Graphs & Matrices

Based on Wasserman and Faust (1994) Chapter 4

A graph is a network model for undirected dichotomous (binary) relations. Self-relations (reflexive ties) are typically excluded. Graphs of directed relations are a special case, considered below on page 4.

SOME BASIC TERMS

In (N,L) two nodes ni and nj are adjacent if line lk = (ni, nj) is in the set of lines L. A node is incident with a line (and vice versa) if that node is one of the two nodes defining the line.

Graph G (N,L) is represented as a sociogram of labeled points and lines in two dimensional space, with arbitrary node locations and line lengths.

A subgraph consists of a subset of the nodes and/or lines of graph G . Dyads and triads are noteworthy two- and three-node subgraphs.

DEGREE d(ni): The number of lines incident to a node (range is from 0 to g-1). Sally has degree 2, Dick degree 3. (See W&F pp. 100-101 for mean & std. dev.)

DENSITY: The proportion of present ties to the maximum possible lines in a graph. Ranges from 0 to 1.0 (for a complete graph). Calculate density of a gXg graph as:

[pic]

Find the density of the 5-node graph above: _________.

Walk (W) is a sequence of incident nodes + lines; length is the number of lines in a walk. Tom-Harry-Betty is length 2, Sally-Dick-Harry-Betty is length 3.

Trail is a walk with distinct lines, altho nodes may appear more than once. Tom-Harry-Betty-Dick-Harry-Sally has length 5.

Other special terms are closed walk, tour, cycle (pp. 107-108)

PATH: A walk with all distinct nodes and lines. The length of a path (number of lines) is its path distance.

Nodes ni and nj are reachable if at least one path of any length connects them.

Several paths may exist between a pair of nodes. The shortest path between two nodes is a geodesic. Its length is the geodesic distance or just distance, (d(i,j). How many paths connect Sally & Betty, what is/are their geodesic(s), and their distance(s)?____________________________

GRAPH CONNECTIVITY

A graph is connected if all pairs of nodes are reachable. A graph is disconnected if some pairs of nodes have no paths connecting them. A single node is an isolate if none of the other g-1 nodes can reach it.

Graph component is a connected subgraph (a maximal connected subgraph): a path exists between all pairs of nodes in the subgraph. Here’s a completely connected graph that is also a single component:

A node is a cutpoint if its removal disconnects the graph (i.e., creates two or more graph components). Node n5 is a cutpoint because its deletion creates two components:

A line is a bridge if its removal results in disconnected subgraphs. Line (n3, n5) is a bridge because its deletion creates two components:

“Cohesive” graphs have relatively frequent lines, many nodes with large degrees, short or numerous paths & geodesics. A “vulnerable” graph is more likely to be disconnected by removal of a few nodes or lines.

Special types include tree, forest, and bipartite graphs (119-121).

DIRECTED GRAPHS

Directional relations can be represented as directed graphs (digraphs). A line with arrowheads indicates the origin/sender and the receiver of a relation for an ordered pair of nodes and (dyad). Two-head arrows indicate mutual ties (reciprocal relations).

The 3 main types of directed dyads are mutual, asymmetric, and null (MAN)

Most terms for undirected graphs have parallels in digraphs. Nodal indegree dI(ni) and outdegree dO(ni) have different values when choosing and being chosen differs for a node. Indegrees measure sociometric “popularity” or “receptivity” while outdegrees indicate “expansiveness.” Find the in- and outdegrees of each actor:

Types of nodes in a digraph depend on the combination of in- & outdegrees:

| |INDEGREES |

|OUTDEGREES |>0 |0 |

|>0 |carrier (ordinary) |transmitter |

|0 |receiver |isolate |

The computation of digraph density now requires that every directed line be tabulated separately. If density = 1.00 then all dyads are mutual.

[pic]

How does the density of the digraph above compare to its nondirected counterpart?

A semipath is a sequence of distinct nodes, where successive pairs are connected by lines, regardless of the lines’ directions. Tom-Harry-Sally-Dick

Digraph reachability requires a directed path sequence connecting nodes i and j. Note that although ni may be reachable from nj, the reverse may not be true. What are examples in the diagram above of ordered dyads reachable in one direction but not in the opposite direction? What dyads are reachable in both directions?

Similarly, four types of dyadic connectivity and digraph connectivity depend by whether nodes are joined by semipaths or paths (see term definitions in W&F pp. 132-133).

Geodesic distances also take line directions into account; hence, d(i,j) may differ from d(j,i). If no path links an ordered pair, their geodesic doesn’t exist and the distance in undefined.

An isolate has “infinite” distance from all others; it’s distance really is not defined.

SIGNED & VALUED GRAPHS

For both undirected and digraphs, the lines of a signed graph carry + or – signs (valences), thus indicating three possible states of a relation (positive, negative, null). An affection relation might have states of love, hate, and indifference.

Valued graphs have numerical values, vk, attached to the lines that measure the magnitudes of interaction, i.e., the strength of the dyadic relation.

Many social ties can be valued: frequency of sexual activity; strength of friendship; cost of goods puchased; number of strategic alliances announced

Density averages the magnitudes of observed ties across all possible ties

[pic]

W&F (143-145) discuss the valued graph analogs to walks, paths, reachability, and path lengths. Computer programs may not always preserve relational values in their computations, so proceed with caution.

MATRIX OPERATIONS

A sociomatrix (adjacency matrix), designated by a boldface capital letter such as X, is the most common matrix form for presenting the social network information in a graph G . (See W&F p. 152 for a discussion and example of the rarely used “incidence matrix.”) A sociomatrix is a square gXg array of the graph’s N nodes displayed in the rows and columns in identical sequential order.

The g2 cell elements, denoted by lowercase xij, are the values of the L lines in the graph, with a distinct value for every ordered nodal pair. Row actor i sends a relation to receiver in column j. In graphs of nondirected lines, all pairwise cells have equal values, xij = xji (i.e., the matrix is symmetric). But a sociomatrix of directed lines may have pairwise values are not equal. For example, in a binary graph if i sends to j but j does not send to i, then xij = 1 and xji = 0. If the pair reciprocates ties, then both cells will have the same value.

Matrix algebra is a branch of mathematics that studies properties of matrices and rules for their transformation. Because network analysis programs such as UCINET embed these principles in their subroutines, we don’t need an extensive knowledge of matrix algebra to be able to run standard analyses. However, as you develop your network analysis skills, you may discover the need for some nonroutine matrix manipulations. UCINET has a Matrix Algebra program (in the “Tools” dropbox) which allows users to write commands. The following description of basic matrix operations (pp. 154-164) may be useful to start developing these skills on your own.

n1 n2 n3 n4 n5

n1 BETTY 0 1 1 0 0

n2 DICK 1 0 1 1 0

n3 HARRY 0 1 0 0 1

n4 SALLY 0 0 1 0 0

n5 TOM 0 0 0 0 0

The size or order of a matrix is defined by its number of rows and columns, designated as “rXc” and spoken as “row by column.” The square sociomatrix above has order 5X5 (“five by five”). Rectangular matrices often have differing numbers of rows and columns. A matrix whose elements are the numbers of factories owned by 500 multinational corporations located in 120 countries would have order 500X120.

In square matrices, the main diagonal cells (i,i) usually have zero values, indicating absent or undefined self-choices. Important: main diagonal values of 0 usually must be included in matrix data for most computer programs.

Symmetrize a square matrix for a digraph by replacing the (i,j) and (j,i) cells with the same value. Apply a rule such as using the minimum, maximum, average, or some other function. If the rule is to use the minimum, replace the larger of the xij and xji values with the smaller one. If the rule is to use the maximum, replace the smaller of the xij and xji values with the larger one.

To symmetrize a network with UCINET, use the “Transform/Symmetrize” dropbox. In the “Symmterizing method” slot, choose “Minimum” or “Maximum” depending on whether both members of a dyad must report directed ties for a mutual connection or whether a report by only one member is necessary to establish a dyadic link, respectively.

For example, here’s the maximum symmetrization of the five-actor matrix above. Notice what happened to Harry’s ties:

n1 n2 n3 n4 n5

n1 BETTY 0 1 1 0 0

n2 DICK 1 0 1 1 0

n3 HARRY 1 1 0 1 1

n4 SALLY 0 1 1 0 0

n5 TOM 0 0 1 0 0

Permute a matrix by reordering the sequence of nodes in the rows and/or columns. Blockmodeling uses permutation to reveal the pattern of actors clustered into discrete positions. Use the “Data/Permute” dropbox to identify the rows and columns to be interchanged.

Transpose a matrix by interchanging the rows with the columns. The transpose of matrix X is designated by a prime, X’. Use the “Data/Transpose” dropbox. Here’s the transpose of the original five-actor matrix:

n1 n2 n3 n4 n5

n1 Betty 0 1 0 0 0

n2 Dick 1 0 1 0 0

n3 Harry 1 1 0 1 0

n4 Sally 0 1 0 0 0

n5 Tom 0 0 1 0 0

Matrix addition and subtraction of two “conformable matrices” (having the same order) creates a third matrix by summing or subtracting values in the corresponding i,j cells. EX: X + Y = Z where the i,jth entry of matrix Z is zij = xij + yij.

In UCINET, use the “Tools/Matrix algebra” dropbox to open the Matrix Algebra Command Window. Write commands in the slot at the bottom then hit the computer’s Enter key to submit. The top screen will show whether the commands executed correctly. The resulting matrix will be saved in your designated directory and can be viewed with the display function. Click the “Help” key to obtain more information about available matrix algebra commands.

As an example, suppose we want to add the original matrix and its transpose. Submit this command:

5-Node_Summed = add(5-Node_Matrix,5-Node_Matrix-Transp)

Notice that a comma separates the matrix names. The resulting summed matrix is symmetric:

1 2 3 4 5

B D H S T

- - - - -

1 Betty 0 2 1 0 0

2 Dick 2 0 2 1 0

3 Harry 1 2 0 1 1

4 Sally 0 1 1 0 0

5 Tom 0 0 1 0 0

Matrix multiplication is used in computing walks, paths, reachabilities, and geodesic distances. Matrices must be conformable for multiplication: for XY=Z the number of columns in X must be equal the number of rows in Y, while the resulting Z matrix will have order equal to X’s rows and Y’s columns. (Although XY may be conformable for multiplication, YX may not be.)

Multiply pairs of elements in a specific row i of X and column j of Y, then add these subproducts to obtain the i,jth cell value of output matrix Z (see example p. 158)

Here’s the original matrix 5X5 X multiplied by a 5X2 matrix Y, which is possible because the number of columns in X equals the number of rows in Y. (Why is the YX multiplication not possible?) The result is a 5X2 matrix Z:

Raising X to a power (square, cube, etc.) involves self-multiplication; e.g., X2 = XX, X3 = XXX. Can you show that squaring the original matrix produces this matrix:

To multiply the original 5-actor matrix by itself in UCINET, use the “Tools/Matrix algebra” dropbox to open the Matrix Algebra Command Window and enter this command:

5-Node_Squared = prod(5-Node_Matrix,5-Node_Matrix)

The results:

1 2 3 4 5

B D H S T

- - - - -

1 Betty 1 1 1 1 1

2 Dick 0 2 2 0 1

3 Harry 1 0 1 1 0

4 Sally 0 1 0 0 1

5 Tom 0 0 0 0 0

[pic]

-----------------------

● BETTY

DICK ●

● TOM

SALLY ●

HARRY

●

n5

●

n2 ●

● n4

n3 ●

n1 ●

●

n7

● n6

● n6

●

n7

HARRY

●

● n4

n3 ●

n1 ●

n2 ●

● n6

●

n7

n5

●

● n4

n3 ●

n1 ●

n2 ●

SALLY ●

● TOM

DICK ●

● BETTY

0 1 1 0 0

1 0 1 1 0

0 1 0 0 1

0 0 1 0 0

0 0 0 0 0

X

0 2

2 0

2 2

2 0

0 2

Y

(0*0 + 1*2 + 1*2 + 0*2 + 0*0 = 4) (0*2 + 1*0 + 1*2 + 0*0 + 0*2 = 2)

(1*0 + 0*2 + 1*2 + 1*2 + 0*0 = 4) (1*2 + 0*0 + 1*2 + 1*0 + 0*2 = 4)

(0*0 + 1*2 + 0*2 + 0*2 + 1*0 = 2) (0*2 + 1*0 + 0*2 + 0*0 + 1*2 = 2)

(0*0 + 0*2 + 1*2 + 0*2 + 0*0 = 2) (0*2 + 0*0 + 1*2 + 0*0 + 0*2 = 2)

(0*0 + 0*2 + 0*2 + 0*2 + 0*0 = 0) (0*2 + 0*0 + 0*2 + 0*0 + 0*2 = 0)

=

=

4 2

4 4

2 2

2 2

0 0

Z

0 1 1 0 0

1 0 1 1 0

0 1 0 0 1

0 0 1 0 0

0 0 0 0 0

0 1 1 0 0

1 0 1 1 0

0 1 0 0 1

0 0 1 0 0

0 0 0 0 0

1 1 1 1 1

0 2 2 0 1

1 0 1 1 0

0 1 0 0 1

0 0 0 0 0

=

X

X

X2

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download