# Link Pruning for Community Detection in Social Networks
## 1 Introduction  
The importance of data has increased steadily in modern society. The rapid changes and advancements in big data analysis over the past decade have received considerable attention from researchers. Accordingly, more benefits in artificial intelligence and deep learning technology, which contribute to developing industries, cannot be obtained without data management and processing technologies. The shape and information of data have become more diverse and complex, and the demand for data applications has increased simultaneously. This demand has increased the interest of researchers in graph mining technology, which can help analyze relationships and interactions of data. Graph mining is one of the fundamental problems in social network analysis, which has numerous applications [1]. Furthermore, the development of deep learning technology for graph data analysis has recently garnered the attention of researchers and industries [2]. Graph modeling provides a useful way to represent and analyze unstructured and complex data. Practical graph mining requires the understanding of data characteristics and appropriate application problems. The first step for successful graph mining is to model a given dataset of interest as a graph or convert a given graph dataset to a transformed graph that can be easily utilized. That is, each data element can be represented as a node, and the interactions or relationships between nodes are represented as links. The characteristics of nodes or links can be modeled as attributes. After that, graph representations can be used to solve machine learning problems through supervised learning or unsupervised learning. In particular, community detection (or graph clustering) is a technique for finding the community structure, with dense links joining nodes of the same community and comparatively sparse links joining nodes of different communities [3]. Thus, communities are regarded as groups of nodes that likely share common properties or play similar roles within the graph. In this paper, we propose a new community detection algorithm for undirected graphs by removing unimportant connections with low values of some link attributes. We present three link attributes for the link removal process, which are appropriate for measuring the strength of local connections in social networks: (i) Jaccard's index (which we call Jaccard), (ii) the number of common triangles (which we call CommonTriangles), and (iii) the Forman-Ricci curvature (which we call Forman-Ricci). These three link attributes consider substructures surrounding two adjacent nodes, and a denser substructure implies a higher link attribute. Using the link attributes, we propose a new framework called link pruning that eliminates links with low values of attributes to identify an enhanced community structure on the resulting pruned graph with low mixing. After link pruning, the transformed graph could be sparse, but the local communities are easier to detect. We call them enhanced communities. We theoretically prove that link pruning effectively detects enhanced communities using the stochastic block models. In addition, we empirically show that clustering with link pruning achieves better performance than clustering with a traditional graph sparsification. Extensive experiments were conducted using both synthetic and real-world networks. Before identifying the community structure, we confirmed that link attributes differ depending on whether the links in the graph are connected between nodes within the same community or different communities. Finally, we verified that a sparse graph with an enhanced community structure was obtained when the link pruning rate was increased based on attribute values through experiments. To evaluate the clustering accuracy, we used the Normalized Mutual Information (NMI) [4; 5] for synthetic networks with the ground-truth community structure and the modularity [6; 7] for real-world networks. Overall, the contributions of this paper are summarized as follows.