Abstract
One of the most important aspects of social network analysis is community detection, which is used to categorize related individuals in a social network into groups or communities. The approach is quite similar to graph partitioning and, in fact, most detection algorithms rely on concepts from graph theory and sociology. The aim of this chapter is to aid a novice in the field of community detection by providing a wider perspective on some of the different detection algorithms available, including the more recent developments in this field. Five popular algorithms have been studied and explained, and a recent novel approach that was proposed by the authors has also been included. The chapter concludes by highlighting areas suitable for further research, specifically targeting overlapping community detection algorithms.
TopCommunity Detection Algorithms: New And Old
Traditional View of Communities in Social Networks
Most community detection algorithms consider a model in which each individual in a network belongs to a single community. The individuals in this community will have many connections with each other but will have a minimal number of connections to individuals belonging to other communities. In fact, this very phenomenon is exploited by nearly all of the community detection algorithms prevalent in social network analysis.
Key Terms in this Chapter
Granule: A granule is a collection of similar, indistinguishable objects that can be treated as an independent unit.
Embeddedness: Embeddedness is the extent to which a pair of granules overlap.
Graph: A graph is a network of nodes, or vertices, and their interconnections, or edges.
Role Players: Role players are important nodes performing unique functions in a social network.
Community: A community is a subset of nodes in a social network that have dense connections between them and which are sparsely connected to nodes belonging to other communities.
Social Network: A social network is a set of individuals that are interconnected through some relationship.
Edge Betweenness: The betweenness of an edge is the number of shortest paths between vertices that contain the edge.
Modularity: Modularity measures the quality of community partitions formed by an algorithm. It is the difference between the actual density of intra-community edges and the corresponding connections in a random network possessing the same degree distribution as that of the actual network.