Motivation:
Community structures is not always representative for the structural distribution of nodes of a graph. Bipartite and cyclic graphs are structured but they are not community structures. To generalize community detection, we can resort to the role extraction problem or it is sometimes called block modeling problem.
Role Extraction
The goal of role extraction is to reduce a large, potentially incoherent network to a smaller comprehensible structure that can be interpreted more readily. The smaller structureed graph is called the reduced graph wherer nodes are grouped together in roles based on their interactions with nodes in either the same role or different roles. The role extraction problem is a generalization of the disjoint community detection problem where each node in a community mainly interacts with other nodes within the same community.
Role extraction, as an empirical procedure, is based on the idea that units in a network can be grouped according to the extent to which they are equivalent, according to some meaningful definition of equivalence, such as structural and regular equivalence etc.
Algorithms for Role Extraction:
- Modularity maximization
- Direct Quality Function
- Indirect Quality Function
- Clustering Algorithms
- Simulated Annealing
- Browet et al.'s Fast Community Detection Algorithm
- K-means Clustering
- Statistics for optimal number of roles:
- Silhouette Statistic
- Gap Statistic