Community Detection Algorithms Flashcards
Walktrap Algorithm
A community detection algorithm that uses random walks to capture the community structure by grouping nodes that are frequently visited together. For example, Walktrap can identify clusters in social networks by analyzing the flow of information between users.
Girvan-Newman Algorithm
A divisive hierarchical clustering algorithm that detects communities by iteratively removing edges with the highest betweenness centrality, which measures the number of shortest paths passing through an edge. For example, the Girvan-Newman algorithm can identify community boundaries in a social network by removing inter-community links.
Label Propagation Algorithm (LPA)
A fast and simple algorithm that assigns labels to nodes, allowing them to adopt the most frequent label among their neighbors. This process iteratively continues until a consensus is reached. For example, LPA can quickly detect communities in large-scale networks, such as identifying groups of similar interests in a social network.
Infomap Algorithm
An information-theoretic approach that models the network as a random walk to minimize the description length of a path taken by a random walker. This algorithm efficiently partitions the network into communities by optimizing information flow. For example, Infomap is used to uncover community structures in citation networks based on shared research topics.
Spectral Clustering
A method that uses the eigenvectors of a graph’s Laplacian matrix to project nodes into a lower-dimensional space, where clustering algorithms like k-means are applied. For example, spectral clustering can detect community structures in complex networks such as protein interaction networks.
Modularity-Based Clustering
A method that aims to maximize modularity, a measure of the density of links inside communities compared to links between communities. For example, maximizing modularity can identify cohesive groups in social networks, enhancing the understanding of social structures.
Hierarchical Clustering
A method that builds a hierarchy of communities using agglomerative (bottom-up) or divisive (top-down) approaches. For example, hierarchical clustering can organize biological networks into nested communities to reveal functional relationships between proteins.
Stochastic Block Model (SBM)
A probabilistic model that divides a network into blocks or communities by assuming nodes within a block are more likely to connect. For example, SBM can model social networks by capturing patterns of connections between different social groups.
Clique Percolation Method
A technique that identifies communities by finding overlapping cliques (fully connected subgraphs) and merging them to form larger communities. For example, this method can detect overlapping communities in collaboration networks, where individuals belong to multiple groups.
