1. Community detection
2. Community detection in networks
Identifying cliques and calculating assortativity and reciprocity provide us with some information as to patterns of vertex association in a network.
A more formal way of achieving this is through community detection.
If a network is said to have a community structure then it is possible to assign vertices to unique sets.
Within each set of vertices, the connections between members will be more dense than the connections between different sets of vertices.
You can see from this network example that the 16 vertices can be assigned into three groups. Within each group - red, blue and yellow, vertices are much more likely to be connected to other vertices of the same color than have edges going to non-group members.
You will often hear these types of groups referred to as 'communities', though they may also be called 'modules', 'groups' or 'clusters' depending upon your subfield.
In real world networks, community structures are very common and community detection can be very useful, particularly in large networks, as it helps us identify functional subunits of a network.
Examples would include cliques in a high school network or voting coalitions in congress.
3. Fast-greedy detection
Although the general principle behind community detection is relatively straightforward - to identify those vertices that are more closely tied to each other than to others in the network - finding communities can be computationally very demanding - especially for large networks.
Nevertheless, many algorithms have been developed and igraph contains several of them. With your own data you should try using different ones to determine which appears to be the most useful as they all have different strengths and weaknesses.
In this section, you will use two different methods - the "fast-greedy" method and the "edge-betweeness" method.
Fast-greedy is a modularity based method - it works by trying to build larger and larger communities by adding vertices to each community one by one and assessing a modularity score at each step. The modularity score is an index of how inter-connected edges are within versus between communities.
In igraph it can be performed by applying the function fastgreedy-dot-community() to the graph object. Printed to console are the community memberships of each vertex.
4. Edge-betweenness detection
In contrast to fast-greedy, the edge-betweenness is a divisive method - it works by dividing the network into smaller and smaller pieces until it finds edges that it perceives to be 'bridges' between communities.
5. Getting community information
Each community detection function produces several pieces of information in a community object. Using the functions length(), sizes() and membership() it is possible to quickly extract information about how many communities there are and which vertices are in which community.
In igraph, it is also possible to make quick plots of the network which show each vertex in its community by color. To do this, the community object and graph object are included as the two arguments to the plot function.
6. Let's practice!
Time to put this into practice.