# A Scheme to Design Community Detection Algorithms in Various Networks
## 2 Related Work  
The research of community detection starts from solving practical problems. For instance, Kernighan-Lin algorithm [4] clusters digital components into similar size groups with the minimized inter-group connections. In this way, engineers decrease the electronic device costs and enhance their stability.  
Conventionally, real-world networks are represented by nodes and edges. Two nodes connected by edges have some kind of relations. Although the meanings of relations vary in different problems, there are two main types: two nodes are related if  
1. There is material transmission between them, and/or
2. they share some identical or similar properties.  
The material here represents concrete objects (like goods) or information (like data packages). A typical example is the transportation among cities. The cities among which people can easily travel have stronger relations and could be considered as a community [29].  
Node attribute similarities also derive relations. In protein-protein interaction networks, biologists cluster proteins with equivalent or similar functions into one group [30]. Here, the relations are their function similarities. In social networks, the people active in similar locations and/or the time slots could be considered as a community. Here, the relations are the location and schedule similarities.  
Based on graph models, lots of community detection algorithms have been proposed.  
Graph partitioning method groups the vertices into a predefined number of communities and minimize the number of edges among them. The algorithms belonging to this method can perfectly solve many practical problems. However, they cannot be adapted to community detections as the algorithms require a pre-specified number of groups that is generally unknown in a community detection problem [1]. In addition, the graph partitioning method is not derived from an explicit definition of communities. Thus, there is no guarantee that the method finds the vertex groups consistent with our intuitions.  
Real-world networks commonly have hierarchical structures from which the abstracted graph models are usually inherited. The related detection algorithms fall into two categories: agglomerative (bottom-up) approach and divisive (top-down) approach [5]. Briefly, the agglomerative approach starts by considering each node as a community and merges the community pairs while moving up the hierarchy. The divisible algorithm works in the opposite way. It starts by grouping all the nodes in one cluster and performs splitting recursively as moving down the hierarchy.  
Partitional clustering also plays an important role in the graph clustering family. In order to apply the algorithm, the user must specify the number of clusters. Thus, it has the same disadvantages as the ones belonging to graph partitioning [1]. The method puts all nodes in a metric space, and thus the distance between each pair of the nodes in the space is defined. The distance here can be considered as a measure of the dissimilarities between the nodes. The algorithm needs to cluster the nodes into a fixed number of groups to minimize a pre-specified cost function.  
All community detection methods and techniques related to matrix eigenvectors belong to spectral clustering. The clustering method requires a distance function to measure the similarity among the objects. The fundamental idea of the algorithm is to use eigenvectors to cluster objects by connectedness rather than the distance. Although there are many successful applications in image segmentation and machine learning, researchers have already found several fundamental limitations. For instance, spectral clustering would fail if it uses the first \(k\) eigenvectors to find \(k\) clusters but confronts with clusters of various scales regarding a multi-scale landscape potential [31].