When analysing a network, a prior substantive interest may drive the analysis to search for subnetworks within the network. Or, put in a different way, whether there are parts of the network that are more cohesive than others. Those parts of a network that are more connected among themselves compared to connections with other parts, might be the site of shared understanding, for instance. Or, we sometimes hear of clique which implies exclusion. Here we only focus on two measures of cohesion that is component and k-cores.
We will build our definitions to arrive at a definition of component. An undirected network is connected if each pair of vertices is connected by a path. In making this connection, the direction of relationship must be respected. Two arcs a → b and b → c implies a path from a to c (a → b → c); however they do not imply a reverse path (b → a; nor c → b → a). Equivalently, a directed network is strongly connected if each pair of vertices is connected by a path. Slightly different, a directed network is said to be weakly connected if in tracing the 'path', the direction of relationship is not respected. That is, there is a weak path from c to a or c — b — a in the above example.
A directed network might not be strongly connected but only weakly connected. We can only link all pair of vertices by disregarding direction; if we respect direction, we won't be able to connect all pairs.
A component is a maximal connected subnetwork. Maximal in the sense that nothing can be added without destroying the property of connectedness. A strong component is a maximal strongly connected subnetwork. If we find a maximal connected subnetwork only by disregarding direction, we have a weak component. The definition of strong component is more strict than that of weak component. Hence, it is easier to find weak components than strong components.
In simple networks, the presence of many components imply isolations. There are parts that are not connected to other parts. In directed networks, there might be no isolations, although there are many strong components. In this case there is no path connecting one component to the other component.
Examples of strong components are given below using network data on visits among San Juan Sur families from de Nooy et al. 2005. This is achieved in Pajek using the sequence: and specifying 3 as the minimum size of components. (In this case, a subnetwork of less than three is considered uninteresting). The sociogram on the right gives all vertices different colours according to which components they belong to. Vertices in turquoise belong to no strong component in this case; Pajek gives them component number zero. The assignment of component number to colour is always available by choosing, in Draw Window, the sequence . In that way we know that yellow vertices belong to component one. In Pajek terms they belong to partition one.
To reduce clutter, reciprocated arrows a → b and a ← b have been replaced with a single edge a — b. The sociogram on the left is one of the components, specifically, component one whose vertices are colored yellow on the complete sociogram. The right part of the complete sociogram and this first component make a useful illustration of the maximal property. No other vertices on the right part of the complete sociogram, or any other vertices for that matter, can be added to this component without destroying the strict connectedness of any pair of vertices in this component. And that includes vertex number 20 which seems to be very close to many member of this component.
A note about selecting a component in Pajek. As a result of search for strong components, each vertex is given a component number, an integer, and equivalently a colour. Refer to the above description to find colour-partition assignment. To draw a sociogram reflecting this new numbering scheme or this new partition, in Pajek Window use the sequence . Of course, if you often do this, just make use of the shortcut Control+P. All along, make sure that the network object is the original network: 1. C:\temp\SanJuanSur.net (75); and the partition is its strong components with size three or more: 1. Strong Components of N1 [>=3] (75, comp.=6).
Extraction of partition one for instance or, in this case, component one, is effected by this sequence then give the lower and higher numbers of partitions to be extracted. Of course, one and only one partition is extracted if both numbers are the same (1 and 1) as in the above example.
|
|
An often used alternative to components is k-core, where k stands for degree. A k-core is a maximal subnetwork in which each vertex has at least degree k within the subnetwork. We can view k-core as a relaxed definition of cohesion. If in a cohesive subnetwork of size 5, vertices are connected to at least 3 others, we have on our hands a 3-core.
Because this visits network is a directed network, it is possible to find its k-core based on incoming and outgoing relations, and also a relation that does not take direction into account. In the last case you need to symmetrise the network, otherwise reciprocated links will be counted twice. . Having consider all that, here are the sequences for finding k-cores in this network: .
Below is the input k-core (left) and the all k-core (right)of the visits network. Only by looking at all k-core, instead of the strict input or output k-core, can we detect some parts that are quite cohesive in this network. The red vertices, corresponding to 3-core, consist of 7 families that quite often visit each other.
 |
 |
Exploration of subnetworks often turns up interesting properties of real networks. Methods for this purpose are not only limited to components and k-core presented here. In fact, more developments, applications and resources are available for your own exploration. You can start by following links collected here.
| Back to Introduction to Social Network Analysis | Back to top |
© G Tampubolon - 17 December 2004