Graph Theory

Specific Definitions

Applying graph theory as a tool to social network analysis allows network data, which generally are expressed by matrices, to be translated into formal assumptions. Graphs within the framework of social network analysis describe a system of interrelated objects. In graph theory, a network is defined as a clearly specified set of nodes, N = {n1, n2,…, ng}, as well as the corresponding set of lines, L = {11, 12,…, 1L}, which connect the nodes. In other words, for the analysis of networks within the framework of graph theory, the definition of social entities is essential. Social entities do not necessarily have to be individuals; they may also be a collective of persons or even juristic persons such as corporations or states.

On the other hand, the definition of the modality of connections between those entities is needed. These connections, for instance, can be relations based on exchange, communication, emotions, power, or cognition. In doing so, the nodes symbolize the particular actors in graph theory. The lines, however, represent their appropriate relations. As the terminology is not completely standard, the terms vertices or points are used for nodes, and edges or arcs are used for what in this discussion are called lines. If two actors are connected directly by a line, they are understood to be adjacent and building the neighborhood. The size of the point's neighborhood is measured by its degree (of connections).

It is crucial to keep in mind that graphs always mean, in this situation, the combination of nodes and lines—not only do the lines represent a graph and not only one single connection between two nodes, but the whole composition of all given links form a graph. Furthermore, neither the position of the nodes in the plane nor the length of the lines is of any importance. The lines do not even have to be straight; straight lines are only conventionally used in matters of clarity within the drawing of the network. This means that one specific network may have more than one definite appearance (see Figure 1).

Figure 1 Three Different Drawings of One Single Graph

The very complex drawings of social networks are well known and sometimes also very impressive in their complexities. If the drawing of complex networks gets too confusing, it is useful to divide the graph into two or more subgraphs. Although a random division of graphs is possible, the criteria for it mostly depend on the particular research interest.

To increase the intricacy of graphs, lines can be supplemented by arrows, which indicate the relational direction between two nodes. Those graphs, whose nodes are connected by directed lines, are called directed graphs, or digraphs (see Figure 2). This means that a directed graph may, for example, indicate the direction of the communication flow, the movement of capital, or the imbalance of power between two actors. If there is no direction indicated, the graph is called undirected.

...