It is beyond the scope of this appendix to expound a fully fledged graph theory. The purpose of the appendix is to give a description of graph theory at a level which provides non-mathematicians with a working knowledge to analyze the main properties of social networks.

Graph theory is the study of graphs, mathematical structures, used to model pairwise relations between entities. It is visually made of vertices or nodes connected by edges. These relations can be directed or undirected. Directed relations mean that the interaction is one-way between the influencer and the influenced. Relations can be bidirectional, meaning that the influence between the two actors is reciprocal.

There are two alternative formalisms which yield representations either by a diagram of nodes and edges or by a matrix that codes the ties between pairs of nodes. They contain the same information and thus any one can be derived from another. Each representation has some advantages. A diagram delivers an immediate visual understanding of the network structure, whereas the matrix representation is better suited to carry out quantitative manipulations of network properties.

Three illustrative networks are shown in Figure A1.1 in both formalisms.

In the matrix formalism, each column and each row represents a node. At the intersection of a column and a row each representing a node, 0 means that no relation between the two nodes exists and 1 means that a relation between the two nodes exists. Figure 1 clearly demonstrates that at first sight it is difficult to derive the topology of the networks from the matrices.

The general notation for the value of the tie from n_i to n_j nodes is written as x_ij with i ≠ j on a certain relation H. When multiple relations exist, the value of the tie from n_i to n_j nodes is written as x_ijr with i ≠ j on a relation H_r.

Connection networks described in section 6.3.1 are an example of graphs used within a specific framework to represent the relations between actors and events (or activities). In such a representation, the interaction between actors indirectly takes place by sharing the same event or activities. The approach to representing interactions between actors by connection networks is grounded in the importance of individuals’ memberships (connections) in collectivities. This modeling tool is especially useful for studying urban social structures or organizational patterns where actors are likely to participate in more than one activity (event). Overlap in group connections allows for information flows between groups and also coordination of the groups’ actions.

Nodes of directed graphs are often classified by using parameters called indegree d_I and outdegree d_O. The indegree of node n_i, d_I (n_i) is the number of nodes adjacent to it, whereas the outdegree of node n_i, d_O (n_i) is the number of nodes adjacent from it. On the basis of these parameters, nodes can be classified as:

• – isolate d_I (n_i) = d_O (n_i) = 0;
• – transmitter if d_I (n_i) = 0 and d_O (n_i) > 0;
• – receiver if d_I (n_i) > 0 and d_O (n_i) = 0;
• – ordinary if d_I (n_i) > 0 and d_O (n_i) > 0.

This typology is useful to describe the roles or positions in social networks.

When dealing with directed graphs, it is necessary to represent each graph by two matrices, one representing the incoming relations to each node and another representing the outgoing relations from each node.

When all the nodes of a graph have ties with all the other nodes, the graph is called complete. The number of ties of a complete graph with g nodes is g(g-1)/2.

Multipartite (bi, tri, etc.) graphs are graphs in which the nodes can be partitioned into several subsets. They highlight the connectivity in a network and make the indirect chains of connection more apparent than the matrix representation. These chains of connection can be useful to explore the long-range correlations between groups of actors when studying change management with the social network model.

When considering relations between subsets of elements, it is useful, when relevant, to distinguish between isomorphism and homomorphism. When two sets are called isomorphic that means that they have the same structural architecture, in other words there is a one-to-one relation between all the elements of the two sets. When two sets are called homomorphic, one-to-many or many-to-one relations exist between the elements of the two sets. Figure A1.2 shows this situation.

The target set in a homomorphic relation has a reduced number of elements with respect to the origin set. This means that the relation between the two sets embodies a constraint of a sort which reduces the variety of elements of the source and, when relevant, can be interpreted as a reduction of leverage for action.

Relations between nodes can be valued to indicate the strength, intensity or specific properties of ties between pairs of nodes. Values can refer, for instance, to interaction frequencies, degrees of acquaintance and so on.

One of the primary uses of graph theory in social network analysis is identifying the most important actors embedded in a network and defined at the individual level or aggregated over a group of actors. Central actors are those extensively involved in relations with other actors. This involvement makes them more visible, being recipients or emitters.

For non-directional relations, a central actor is defined as one involved in many ties. Access or control over resources, brokerage of information, etc., are issues well suited to be analyzed with this concept.

For directional relations, distinction between ties received and ties sent allows for differentiating the status of influencers and the influenced on the basis of the indegree and outdegree parameters.