Concepts from Graph Theory

Social network analysis makes use of concepts from Graph theory and in these materials network and graph are used interchangeably. Briefly, we will be looking at the following concepts: graph, digraph, transpose and symmetrize. A graph G(V,E) consists of a set of vertices V representing individuals or objects and a set of edges E representing relationships between the individuals or objects. An edge (a,b) means that a and b are related or a ↔ b; for instance, a and b are friends. Edge (a,b) also implies edge (b,a), in this way this graph is called symmetric or not directed. This definition of graph is quite suitable to capture friendship relation because (a,b) in this context means both a is a friend of b and b is a friend of a. The number of friends of a is also known as the degree of a or the immediate neighbour of a.

However, if one wants to capture a relationship that is not symmetric or directed such as mentoring, another graph is needed, i.e. a directed graph or digraph G(V,A). It consists of vertices set V representing individuals or objects and arcs set A representing the relationship. An arc (a,b) means a mentors b or a is the mentor and b is the mentee in this relationship or a → b. It follows that (a,b) is not the same as (b,a) and hence the relationship is not symmetric. G is called a directed graph or digraph because one can easily imagine the set of arcs A pictured as a collection of arrows connecting mentors and mentees. In a digraph, each vertex has two kinds of degree, that is indegree and outdegree. To use the interpretation above the outdegree of a is the number of mentees of a; whereas the indegree of a is the number of mentors of a.

If the amount of advice can be measured for instance by frequency or duration of contacts, the arrows can be given values. This results is a valued digraph. Likewise, one can extend the graph definition above, if strength of friendship is of interest beyond whether two individuals are friends or not, one can have valued graph instead of just a graph.

In a mentoring digraph above (a,b) means a is the mentor and b is the mentee; that is one convention to fix the interpretation. Other interpretation might be equally legitimate and leads to changes to the digraph. One can focus on deference or emulation instead and transpose the arc (a,b) into (b,a) which is interpreted as b emulates a. The resulting digraph, made up of the same vertices set V and set of transposed arcs A' is a transpose of G. To sum up, it is important to fix the interpretation of an arc and, by implication, a digraph. And, it is often of possible to have a complementary interpretation by working on a transposed digraph.

Furthermore, digraph G above which captures mentoring relationship can also be looked at from the perspective of information sharing. In this context (a,b) changes meaning; it means a is party to the same information as b which implies that b is party to the same information as a. Again, in this context (a,b) is the same as (b,a). An arc (a,b) or a → b in digraph G has changed because of the perspective or interpretation into an edge (a,b) or a ↔ b. To achieve this effect, the set of arcs in digraph G(V,A) is symmetrized into the set of edges E to result in just a graph G(V,E).

Back to Introduction to Social Network Analysis Back to top

© G Tampubolon - 17 December 2004