The overlapping community discovery algorithm based on the local interaction model

Abstract

In social networks, the traditional locally optimized overlapping community detection algorithm has a free-rider problem in community extension, which mainly relies on the structure information of nodes but ignores the node attributes. Therefore, in this paper, we redefine community based on theoretical analysis and propose an overlapping community discovery algorithm based on the local interaction model. By fusing node attributes and structural information, we first proposed an improved density peak fast search method to obtain multiple core nodes in the community. Then, according to the interaction range and interaction mode of the core node, we established a local interaction model of the core node, which converts the interaction strength or the number of common attributes between nodes in the network into the change of the distance between nodes. Finally, according to the proposed improved clustering algorithm, we obtain the community where the core node is located and merge the communities with a high degree of overlap. The experimental results show that compared with other similar community discovery algorithms, the proposed method outperforms the state-of-the-art approaches for community detections.

Keywords

Social network community discovery overlapping communities local interaction model

1. Introduction

With the development of digital information networks, social networks have become an essential means as a type of complex network structure for understanding and analyzing potential behaviors in people’s daily lives. Based on social networks, we can expand social relationships, get more opportunities for cooperation, and get help from like-minded social friends. A social network is usually a complex system model that simulates various relationships between people in the real world with a graph structure, where nodes are users and edges are various social relationships between users. As an essential characteristic attribute of social networks, the community is described as close connections between nodes in the same community and sparse connections between different communities. It is widely used in public opinion detection, recommendation systems, and other aspects. It has become an essential tool to understand and analyze the structure of social networks.

For a long time in the past, many scholars detected non-overlapping communities mainly based on the structural relationship of nodes [1, 2, 3], that is, the relationship between users. At present, relevant research shows that users may belong to multiple communities due to the complexity and diversity of users’ social relationships in the real world [4, 5, 6]. In social networks, in addition to structural features, user nodes also include attribute features, such as user interests, occupation, and education level, etc. Therefore, how to use the structural characteristics and attribute characteristics of nodes has become a hot topic in current research to obtain overlapping community [7, 8, 9].

At this stage, more and more methods are proposed to detect overlapping communities on the network. However, most of these methods are based on the structural characteristics of nodes, which are mainly divided into clique percolation [8, 9], link partitions [10, 11], and label propagation [12]. These methods can better detect the community structure, but the network’s global structure information must be obtained. When the network information is incomplete, it will be subject to some restrictions. In addition, the local optimization algorithm (LOM) is also an overlapping community discovery algorithm. LOM usually takes the core node of the network as the community center and uses local information to expand the community through optimized functions. Because LOM reveals the structural characteristics of the whole and part of the network, it has more significant advantages in network local feature mining and cost calculation [13]. Besides, LOM does not need to obtain complete network structure information. Therefore, LOM is more suitable to analyze large-scale social networks containing node attribute characteristics [14]. In 2009, Lancichintti et al. [15] proposed a local fitness maximization algorithm (LFM), which randomly selects core nodes, and expands the community where the core nodes are located through the rate of change of the fitness function value. Coscia et al. [16] proposed the DEMON algorithm, which expanded the community union through the neighborhood information of the core node. However, In the discovery community these methods directly affect the community’s quality due to the random selection of core nodes, forming many redundant communities. For this reason, Lee et al. [17] proposed the Greedy Clique Expansion algorithm, which selects the largest clique not less than $k$ as the core node. Ma et al. [18] proposed a group-based local optimization algorithm (LOC). They choose the node with the highest density as the core node and add all k-cliques where the node with the highest adaptability is located to expand the community. Li et al. [19] proposed a local expansion method (CFLEM) based on clustering coefficient and fitness. The algorithm expands the community by adding and deleting nodes in batches, sorts all nodes according to the size of the clustering coefficient, and selects the node with a larger clustering coefficient and has never been visited as the core node. Since nodes in social networks contain structural features and attribute features, the community structure obtained only by relying on the node’s structural information is inaccurate. Besides, wu et al. [20] found the free-riding problem based on the optimization function expansion method. It means that some nodes which are far away from the core node or have nothing to do with the attributes of the core node because they can maximize the optimization function, join the current community, and affect the quality of community discovery.

To avoid the above-mentioned problems, related scholars propose a non-optimized method to obtain overlapping community structure, which uses the attribute characteristics of nodes. Zhang et al. [21] proposed the Tsoca-SA algorithm that fuses node attributes. They obtain public edges (connecting edges between communities) using non-overlapping community discovery algorithms based on structural information. Then, they obtain the final overlapping community structure, by judging the community to which the public node belongs based on the node attribute information. Li et al. [22] designed an attribute network-oriented spectrum community detection method, which combines node structure and attributes characteristics. However, when the network scale is large, or the network information is incomplete, these algorithms cannot obtain the desired results. Fang etc. [23] proposed an ACQ algorithm, which searches for nodes that share neighbors and common attributes with core nodes. Huang et al. [24] regarded multiple nodes as core nodes. It was required that the nodes within the community must be tightly connected, and the distance between nodes must be less than a specific value. They proposed the LocTAC algorithm. The algorithm first calculates the correlation between the core node and its neighboring nodes. Then, the neighbor nodes with higher correlation are added to the community where the core node is located, and the community structure is adjusted according to the attribute information of the node. However, these methods do not consider the degree of overlap between communities. In other words, communities with large overlaps are not merged, and there is community redundancy. Different from the above algorithm, in this paper, we propose an overlapping community discovery algorithm based on a local interaction model (OCBLIM), which combines the structure and attribute characteristics of nodes and takes advantage of the local optimization algorithm. We search for the core nodes of the network according to the improved algorithm and build a local interaction model based on the core nodes. Then, according to the proposed algorithm, we obtain overlapping communities with tight connections and larger attribute correlations between nodes.

The main contributions of our work are summarized as follows. (1) We propose an overlapping community discovery algorithm based on a local interaction model (OCBLIM). (2) We redefine the community based on theoretical analysis. (3) For any given node, we propose a framework model to obtain the community where the node is located. (4) Compared with other similar algorithms on the real data set, the experimental results show that the community divided by the proposed algorithm is generally better among multiple evaluation indicators.

The rest of the paper is organized as follows: Section 2 introduces the concepts related to this article. Section 3 redefines the community based on theoretical analysis. Section 4 discusses the algorithm of this paper in detail, including the search of core nodes and the establishment and solution of models. Section 5 verifies the feasibility of the algorithm proposed through experimental analysis. The last section concludes the paper and indicates the work to be done next.

2. Related technologies

2.1 Social networks

A social network is a graphical description of the actual relationship of users. The nodes in the network not only have social relationships but also contain attribute characteristics. For example, in a co-author network, the nodes represent the authors of the paper. The edges represent the cooperative relationships between authors. The attributes are the authors’ related research directions. The user information we collect and extract usually exists in an unstructured form. In this paper, to facilitate the understanding and analysis of social networks, we structure user information through an ontology model which can be used as a standard modeling tool because it guarantees the interoperability between data [25]. As shown in Fig. 1: A social network consists of three parts: nodes, domain information and communities. Each node can be described as a set of attributes composed of implicit features and explicit features. The explicit features are the user’s external attributes, which are manifested as the user’s demographic attributes, such as gender, education, and occupation, as well as ratings and search records, etc. The implicit features are the intrinsic attributes of users, which can only be inferred from user behavior data. For example, we use user search records as keywords to analyze user interest characteristics. For different application scenarios, different social networks generate different domain information. For example, the information generated by the Twitter network is mainly related to the user’s daily life dynamics, while the information generated by the co-authoring network is mainly the user’s academic expertise. The domain information contains the user’s relationship type. For example, in the Twitter network, users are friends, and in co-authoring networks, users are cooperative. At the same time, domain information also includes domain experts, who play a relatively important role in the development and change of the network. For example, authoritative authors in the co-authored network may can determine the research direction of related industries. Besides, social networks contain different communities, and each community reflects the same theme. For example, in a co-authored network, the same community means that users have the same research direction.

Figure 1.

Social network ontology model.

After the data is structured, we formally define a social network as an undirected graph $G=(V,E,P)$ . Where $V=\{v_{i}\}_{i=1,\ldots,n}$ represents the set of $n$ nodes. $E=\{(v_{i},v_{j},q)|v_{i},v_{j}\in V\}s.t.|E|=m$ represents the set of $m$ edges and $q$ represents edge weight. $P=\mbox{\{}p_{1},\ldots,p_{k}\mbox{\}}$ is the attribute set of the nodes. The attribute vector of the node $v_{i}\in V$ is denoted as $v_{i}=\{v_{i1},v_{i2},\ldots,v_{ik}\}$ , where $v_{ik}$ is the attribute value of the node $i$ in the attribute $p_{k}$ .

2.2 Clustering algorithm

2.2.1 Clustering by Fast Search and find of density peaks

Clustering by Fast Search and find of density Peaks (IDP) is a Clustering algorithm published by Rodriguez et al in Science in 2014 [26]. The main idea of the algorithm is that the cluster center point has a large local density, that is, the number of neighboring nodes, and the minimum distance between the centers of different clusters is as large as possible. The algorithm first determines the cluster center point and the number of clusters by constructing a decision graph. Then, the algorithm classifies the non-class center point $x$ and puts it in the cluster where the point with a density greater than $x$ and closer to $x$ is located.

Because the algorithm can quickly find the cluster center node and the number of clusters in arbitrary shape data, some scholars apply it to social networks to find the core nodes of the community and determine the number of communities [27, 28]. However, this algorithm is only applicable to the Euclidean distance between nodes, and it does not apply to the search for core nodes in social networks containing attribute characteristics.

2.2.2 Canopy clustering

Canopy clustering algorithm [29] is an unsupervised clustering algorithm based on distance proposed by McCallum et al. The execution steps of the algorithm are described as follows: First, the entire data node set group is taken as a list, and an initial threshold $T_{1},T_{2}(T_{1}>T_{2})$ is given. Then, the algorithm randomly selects a data node as the cluster center and calculates the Euclidean distance between the remaining sample points and the cluster center. If the distance is greater than $T_{1}$ , a new cluster is formed. If the distance is less than $T_{1}$ , the sample points are divided into this cluster. If the distance is less than $T_{2}$ , the algorithm deletes sample points from the list until the list is empty. Finally, the algorithm outputs $k$ clusters that meet the conditions. However, the determination of the threshold $T_{1}$ , $T_{2}$ will greatly impact the clustering results of Canopy clustering. If the threshold is too large, data from different clusters will be merged into the same category, resulting in a reduction in the total number of clusters. On the contrary, the total number of clusters will increase, which greatly affects community division accuracy.

Since this algorithm is suitable for large-scale and high-latitude data sets, and has a greater advantage over other clustering algorithms in clustering speed, in this paper, we improve the Canopy clustering to obtain the community structure of the network.

Figure 2.

Schematic diagram of node distance change.

2.3 Problem description

In real life, when we interact with different types of people, we will adopt different ways of interaction, and the scope of our social interaction is mainly concentrated on the neighbors who have contact with us or strange users who have common interests and hobbies. With time, due to frequent interactions and common attributes, the cohesion of users in the same community will be enhanced through mutual influence, while the cohesion of users between communities will be weakened [30]. Cohesion reflects the degree of interaction between nodes and the number of common characteristics. The stronger the interaction and the greater the number of common features between users, the stronger their cohesion. On the contrary, their cohesion is weaker. In this paper, we use the distance between nodes to describe cohesion. If the distance between nodes is closer, the cohesion is stronger, and they are more likely to be in the same community. Conversely, if the distance between nodes is farther, the cohesion is weaker, and they are less likely to be in the same community. Based on this relationship, we convert the complex social network structure into a simple distance measure between nodes. Since the core node is the center of the community, we propose a local interaction model based on the core node’s interaction range and interaction method. We transform community discovery into finding a collection of nodes that are close to the core node. Afterward, we obtain the overlapping community structure according to the proposed method, avoiding the shortcomings of the local optimization algorithm.

Figure 2 is a schematic diagram of the distance change between nodes in the co-author network. In Fig. 2A, a1, a2, and a3 are the core author nodes, and the dotted line indicates that the authors have a joint research direction or have co-published papers. With time, the cohesion of authors with the same research direction or with a strong degree of interaction is enhanced through mutual influence and moves in the direction of decreasing distance. As shown in Fig. 2B, the non-core nodes in the network move to the core nodes to reduce the distance. Simultaneously, because the non-core nodes are connected by a dotted line, they move to their internal directions to reduce the distance. When the distance is not changing, the final stable community structure can be obtained through the clustering method. As shown in Fig 2C, the co-author network is divided into two community structures. Node P is in two communities simultaneously, which is an overlapping node.

3. Key technology

3.1 Community definition

Most of the existing local optimization algorithms rely on the structural features of nodes to obtain the core nodes of the network. The core nodes are defined as nodes with more neighbors and called the center of the community [31, 32, 33]. However, user information includes more than just social relationships. User nodes with frequent attributes but few social relationships in the community can also be called core nodes. Therefore, in the text, we will redefine the core node from two aspects: node neighbors $\Gamma(h)$ and attribute feature frequencies $f(h)$ .

Definition 1 (core node): For $\exists(h\in V)$ , if $h$ satisfies $\Gamma(h)\geqslant\varepsilon\vee f(h)\geqslant\varepsilon$ , $h$ is called the core node.

Besides, due to the complexity of user information, in the process of expanding the community, the community divided by the traditional LOM that only uses the structural relationship of the nodes is incomplete. Although existing overlapping community discovery algorithms combine node structure information and attribute characteristics, they cannot obtain an ideal community structure when dealing with large-scale or incomplete data. Based on this, we put forward two hypotheses, combining user real-life scenarios.

Hypothesis 1: User nodes $v\in V$ and $h$ in the same community $C_{h}$ interact frequently, and satisfy $(\Gamma(v)\wedge\Gamma(h))\geqslant\varepsilon$ . Where $\Gamma(v)$ is the nearest neighbor of the node $v$ .

Hypothesis 2: User nodes $v\in V$ that have common attributes (such as the same interests and preferences) with $h$ may be in the same community $C_{h}$ .

According to the relationship between users, we propose hypothesis 1. For example, in the Weibo social network, well-known users with high influence are followed by many fans. Due to the transitivity of the interaction, there are also connections between users who interact frequently with the core node $h$ , such as fans like, comment, and forward each other. However, the attention generated by the interaction between fans is often less than that of well-known users.

Nature 1: There are frequent interactions among users in the same community $C_{h}$ . ie, for $\forall(v,u\in C_{h})$ , if $(\Gamma(v)\wedge\Gamma(u))\geqslant\tau$ and $\tau\leqslant\varepsilon$ , $v,u\in C_{h}$ .

Hypothesis 2 is proposed based on node attributes. For example, in the coauthor network, ordinary authors in the same direction and authoritative authors with a large number of published papers may come from the same community. Due to the mutual influence between attributes, authors in the same research direction help each other, answer each other’s questions, and jointly complete scientific research goals. However, the experience of communicating with authoritative authors is often greater than that of ordinary authors.

Nature 2: The more attributes shared between users, the more likely they are from the same community. ie, if $(f(v)\wedge f(u))\geqslant\tau$ and $\tau\leqslant\varepsilon$ , the greater the likelihood of $v,u\in C_{h}$ .

Social relationships are manifested as the structural features of nodes, while implicit features and explicit features reflect the attributes of users themselves. Based on two basic hypotheses, we define communities as:

Definition 2 (community, $C_{h}$ ): $C_{h}$ is a collection of users who interact frequently or share common characteristics with $h$ . That is, for $\forall(u\in V)$ , if $((\Gamma(u)\wedge\Gamma(h))\geqslant\varepsilon)\vee((f(u)\wedge f(h))% \geqslant\varepsilon)u$ , $h\in C_{v}$ .

According to Nature 1 and 2, it can be generalized to general conditions. For any given node $v\in V$ , the community $C_{v}$ where the node is located can be defined as:

Definition 3 (community, $C_{v}$ ): $C_{v}$ is a collection of users who interact frequently or share common characteristics with node $v\in V$ . That is, for $\forall(u\in V)$ , if $((\Gamma(v)\wedge\Gamma(u))\geqslant\tau)\vee((f(v)\wedge f(u))\geqslant\tau)$ , then $u,v\in C_{v}$ .

In the same community, since the core node is the center of the community, the core node’s neighbors or the attribute feature frequency is greater than the non-core node, and the value of the parameter $\tau$ is always less than or equal to $\varepsilon$ . It can be concluded that given core node $h\in C_{h}$ , and non-core nodes $v\in C_{h}$ , $C_{h}$ and $C_{v}$ must satisfy $C_{v}\supset C_{h}$ . That is, the community $C_{h}$ where the core node is located is a subset of the community $C_{v}$ where non-core node $v\in C_{h}$ is located.

According to the above discussion, the community based on the core node division satisfies the close structural connection or the attribute characteristics appear frequently in the community. This effectively reveals the community structure of the network and makes the proposed algorithm universal. The remainder of the article, if there is no obvious emphasis, discusses community $C_{h}$ .

4. Overlapping community discovery algorithm based on the local interaction model

Compared with other algorithms, the locally optimized overlapping community discovery method does not need to obtain complete network structure and attribute information, so it is used by many scholars to analyze large-scale social networks. However, there is a free-riding problem in optimization and expansion, which affects community discovery quality. Therefore, in this paper, we obtain the core nodes of the network in advance, and establish the local interaction model of the core nodes, by using the advantages of the local optimization method. Based on this, we have developed an overlapping community discovery algorithm based on a local interaction model (OCBLIM). As shown in Fig. 3, the algorithm is mainly divided into three parts. First, we propose an improved density peak fast search algorithm (ICDP) to obtain several core nodes of the network by combining the structure and attribute characteristics of the nodes. After that, we establish a local interaction model of the core node, based on the core node’s interaction range and method. The degree of interaction or the number of shared attributes between non-core nodes and core nodes is converted into changes in distance. Finally, we propose an improved Canopy algorithm (CI) to obtain the community where the core node is located and merge the communities with a high degree of overlap. In addition, in the process of algorithm execution, the domain information and domain experts of different social network applications will affect the selection of core nodes and the establishment of local interaction models. We will analyze in detail in the algorithm.

Figure 3.

Flow chart of OCBLIM algorithm.

4.1 Find the core node

To make up for the deficiencies of the IDP algorithm, we propose an improved density peak fast search algorithm (ICDP) to find the core nodes of the network. Since nodes contain attribute features, we will redefine related concepts.

Definition 4 (local density, $\rho_{i}$ ) Local density describes the importance of nodes in social networks. The local density of core nodes is higher and greater than that of non-core nodes. The local density of nodes $i$ is expressed as:

$\displaystyle\rho_{i}=\sum\limits_{j\in V}{\chi(||d_{ij}||-||d_{c}||)}$

(1) $\displaystyle\chi(x)=\left\{{\begin{array}[]{l}1\quad\text{if }x>0\\ 0\quad\text{otherwise}\\ \end{array}}\right.$

Where $d_{ij}$ represents the number of neighbors and attributes shared by node $i$ and $j$ and the symbol $||\,||$ represents modulo. We represent $d_{ij}$ as a two-dimensional vector {public neighborhood, public attribute}. The value range of $||d_{c}||$ is the first 1%–2% of all $||d_{ij}||$ values in descending order. Attributes similar to domain information may increase the value of $\rho_{i}$ , and attributes shared with domain experts may contribute more to $\rho_{i}$ . The more neighbor nodes and attribute feature shared by node $i$ and other nodes $j$ , the greater the value of $\chi(x)$ , and the higher the local density of node $i$ .

Definition 5 (minimum distance, $\delta_{i}$ )

$\displaystyle\delta_{i}=\left\{{\begin{array}[]{ll}\mathop{\max\left(\frac{1}{% ||d_{ij}||}\right),}\limits_{j}&\text{if }\rho_{i}=\mathop{\max}\limits_{k}(% \rho_{k})\\ \mathop{\min\left(\frac{1}{||d_{ij}||}\right),}\limits_{j:r_{j}>r_{i}}&\text{% otherwise}\\ \end{array}}\right.$ (2)

When the local density $\rho_{i}$ of node $i$ is the largest, $\delta_{i}$ is the minimum value of $||d_{ij}||$ of node $i$ and other nodes $j$ On the contrary, $\delta_{i}$ is the maximum value of $||d_{ij}||$ of the node $i$ and the node $j$ whose density is greater than the node $i$ .

$\rho_{i}$ reflects the importance of the node in the network, and $\delta_{i}$ represents the possibility that the node is in the same community. To select the core nodes of the network, it is necessary to establish a decision diagram, where $\delta_{i}$ is the vertical axis and $\rho_{i}$ is the horizontal axis. However, it is often necessary to artificially select the core node set $\{h\}$ of the network in the decision diagram. For some complex decision graphs, the core nodes may be chosen more or less [34, 35], resulting in the unsatisfactory community division. In this paper, we introduce core value [36] $\omega_{i}=\rho_{i}\times\delta_{i}$ and core value change rate $\textit{rate}_{i}$ to automatically obtain $\{h\}$ .

Definition 6 (The rate of change of core value, $\textit{rate}_{i}$ ) The rate of change between the $\omega_{i}$ value of the core node and $\omega_{i}$ of the non-core nodes is relatively large. To automatically select the core nodeset $\{h\}$ , $\omega_{i}$ is sorted by size, then $\textit{rate}_{i}$ is expressed as:

$\displaystyle\textit{rate}_{i}=(i-1)\frac{\omega_{i-1}-\omega_{i}}{\omega_{i}-% \omega_{i+1}}$ (3)

According to Eq. (7), the nodeset before the node with the largest value of $\textit{rate}_{i}$ is automatically selected as $\{h\}$ . By automatically selecting $\{h\}$ , the value of the parameter $\varepsilon$ is determined indirectly.

Based on the IDP algorithm, we combine the structural features and attribute features of the nodes, transform the Euclidean distance metric into the reciprocal of the two-dimensional vector modulus, and propose an improved CIDP algorithm, which is applied in social networks to find the core node-set $\{h\}$ . The algorithm first sequentially calculates the local density $\rho_{i}$ and minimum distance $\delta_{i}$ of each node in the social network. Then the nodes are sorted according to the size of the core value $\omega_{i}$ and $\{h\}$ are automatically obtained by calculating the core value change rate $\textit{rate}_{i}$ .

Algorithm 1: ICDP algorithm.

Input: social network $G=(V,E,P)$ .

Output: core node-set ${\{}h{\}}$

1: Initialize, $h=\emptyset$

2: for $i$ in ( $V$ ):

3: $\omega_{i}=\rho_{i}\times\delta_{i}$

4: end for

5: $\textit{sort}(\omega_{i})$

6: for $i$ in ( $\omega_{i}$ ):

7: $\textit{rate}_{i}=(i-1)\frac{\omega_{i-1}-\omega_{i}}{\omega_{i}-\omega_{i+1}}$

8: end for

9: The node-set before the node with the largest change rate $\textit{rate}_{i}$ is selected as ${\{}h{\}}$ .

4.2 Establishment and solution of the local interaction model

Algorithm 1: ICDP algorithm.
Input: social network $G=(V,E,P)$ .
Output: core node-set ${\{}h{\}}$
1: Initialize, $h=\emptyset$
2: for $i$ in ( $V$ ):
3: $\omega_{i}=\rho_{i}\times\delta_{i}$
4: end for
5: $\textit{sort}(\omega_{i})$
6: for $i$ in ( $\omega_{i}$ ):
7: $\textit{rate}_{i}=(i-1)\frac{\omega_{i-1}-\omega_{i}}{\omega_{i}-\omega_{i+1}}$
8: end for
9: The node-set before the node with the largest change rate $\textit{rate}_{i}$ is selected as ${\{}h{\}}$ .

After obtaining the core node of the network, we established a local interaction model of the core node, which calculates the degree of influence between the core node and its neighbors, and changes the relative distance between them. Then, we propose an CI algorithm, which quickly obtains overlapping communities of the network based on the distance between nodes and the degree of overlap between communities.

4.2.1 Local interaction model

The local interaction model takes the core node of the network as the center of the community, and determines the degree of change in the distance between the core node and its neighbors based on the core node’s interaction range and interaction method. The closer the distance, the greater the possibility of belonging to the same community. The core node’s interaction range is limited to the set of nodes that have a structural relationship or similar attributes, and the interaction method depends on the attributes of the node itself. In this paper, we use $\frac{1}{||d_{(h,x)}||}$ as the initial distance $d(h,x)$ between nodes $h$ and $x$ . Based on reality, we summarize the impact of the core node’s interaction range and interaction mode on the initial distance $d(h,x)$ into two aspects: (1) Structural features. (2) Attribute characteristics. Next, we will describe the impact of two aspects on the initial distance $d(h,x)$ .

The node structure is an external feature that represents the relationship between users. In the field of communications, the longer the path taken in the information dissemination, the weaker the accuracy and completeness of the information. Similarly, in a social network, when two user nodes need to establish an interactive relationship, the more nodes they pass, the farther the distance between them.

Nature 3: The longer the shortest path between user nodes, the longer the distance.

In real life, users who have more mutual friends will be closer. For example, users A and B are friends of many mutual friends, which indicates that they have many common interests and show close relationships.

Nature 4: The more paths between user nodes, the closer the distance.

Therefore, according to Nature 3 and 4, we use $D I$ to describe the influence of the node’s structure characteristics on distance $d(h,x)$ .

$\displaystyle DI=-g\left(\frac{n_{(h,x)}}{\Gamma(h)f(h,x)}\right)$ (4)

Where $f(h,x)$ is the shortest path between core nodes $h$ and non-core nodes $x$ , and $n_{(h,x)}$ is the number of paths between nodes. The coupling function $g()$ is represented by $\sin()$ , and the coupling function is used to quantify the change in distance.

The attributes of nodes are implicit characteristics, such as occupation, education, age, and so on. Since different social network applications produce different domain information, the importance of attribute characteristics is not equivalent. Attributes similar to domain information may account for a larger proportion, and the attributes possessed by domain experts may play a decisive role. Because the higher the similarity of the attribute features of the nodes, the stronger the homogeneity. Based on this relationship, we propose node homogeneity $V_{\textit{homo}}$ and node heterogeneity $V_{\textit{hete}}$ as a measure of the influence of attribute characteristics on distance. $V_{\textit{homo}}$ is the similarity of common neighbors between nodes. $V_{\textit{homo}}$ is expressed as

$\displaystyle V_{\textit{homo}}=-\sum\limits_{v_{x}\in=\Gamma(h)\cap\Gamma(x)}% {\frac{g(p(v_{h},v_{x}))}{\min|\Gamma(h),\Gamma(x)|}}$ (5)

Where, $v_{h}$ and $v_{x}$ are attribute vectors of node $h$ and $x$ respectively, $p(v_{h},v_{x})$ is the Pearson correlation coefficient, and $\min|\Gamma(h),\Gamma(x)|$ is the minimum number of neighbors.

$C_{\textit{homo}}$ is the similarity between the exclusive neighbors of node $x$ and $h$ .

$\displaystyle V_{\textit{hete}}=-\sum\limits_{v_{h}\in EN(h),v_{x}\in EN(h)}{% \frac{g(p(v_{h},v_{x}))}{\min|EN(h),EN(x)|}}$ (6)

Where $EN(x)$ is the exclusive neighbor of the node $x$ . If node $x$ and $h$ are connected, the exclusive neighbor of node $x$ is denoted as $EN(x)=\Gamma(h)-\Gamma(h)\cap\Gamma(x)$ , and the exclusive neighbor of node $h$ is denoted as $EN(h)=\Gamma(x)-\Gamma(x)\cap\Gamma(h)$ .

Finally, we get the final update formula of distance $D(h,x)$ , combining the two influence methods.

$\displaystyle D(h,x)=d(h,x)+DI+V_{\textit{homo}}+V_{\textit{hete}}$ (7)

4.2.2 Obtain overlapping communities

In the previous section, we converted the complex network structure into a simple distance measurement between nodes, by using a local interaction model, which greatly simplified the scale of problem-solving. In this section, we propose a CI algorithm that selects the core node as the initial community, expands the community, and merges the communities with a high degree of overlap based on the threshold. By specifying the initial community, the algorithm avoids the influence of the random selection of the threshold on the number of divided communities.

As shown below, we first set the initial thresholds $T_{1}$ and $T_{2}$ . Different from the Canopy clustering algorithm, $T_{1}$ is the clustering parameter and $T_{2}$ is the community fusion parameter. Then, the algorithm takes the core node $h$ as the initial community $C_{h}$ , and obtains the node $x\in\Gamma(h)$ whose distance $D(h,x)$ is less than the threshold $T_{1}$ to join the current community $C_{h}$ , by traversing the neighbors of the core node. Finally, the fusion threshold $T_{2}$ is used to merge communities with a higher degree of overlap to obtain overlapping communities.

Algorithm 2: CI Algorithm.
Input: Core node-set $\{h\}$ .
Output: Community $\{C\}$ .
1. Given initial thresholds $T_{1}$ and $T_{2}$ .
2. for $h$ in $\{h\}$ :
3. $C_{h}\leftarrow h$
4. for $x$ in $\Gamma(h)$ :
5. if $D(h,x)<T_{1}$ :
6. Node $x$ is added to the community $C_{h}$
7. end if
8. end for
9. end for
10. The threshold $T_{2}$ is used to determine whether the community can be merged

Algorithm 3: OCBLIM Algorithm.
Input: Community network $G=(V,E,P)$ .
Output: Overlapping community $\{C\}$ .
1. The core node-set $\{h\}$ is obtained according to the ICDP algorithm
2. The local interaction model of core nodes is established
3. The overlapping community set $\{C\}$ is obtained according to the CI algorithm.

4.3 Algorithm description

In this paper, we propose the ICDP algorithm to find the core node, combining the structure and attribute characteristics of the node. By constructing the local interaction model of the core nodes, we convert the complex network into the distance between nodes. After that, the overlapping community structure is obtained based on the proposed CI algorithm. Finally, combining the above three points, we propose an overlapping community discovery algorithm based on a local interaction model (OCBLIM). The algorithm is mainly divided into 3 parts. The first part is to obtain the core node-set $\{h\}$ according to Algorithm 1. The second part is to establish the local interaction model of the core node. The third part is to obtain overlapping community sets, by using $\{h\}$ as the input of Algorithm 2. The OCBLIM algorithm steps are as follows.

5. Experimental analysis

This section evaluates the proposed algorithm’s efficiency and feasibility through experimental methods, and all experiments use python coding.

5.1 Data set

Table 1
Data set

Dataset	V	E	$\bar{d}$	$\|C\|$	$\|P\|$
Facebook	4039	88234	43.6	193	26
Cora	2708	5429	3.797	7	1432
PubMed	19717	44338	4.497	3	500
Cornell	195	283	2.902	5	1583
DBLP	93432	335520	7.18	4836	735

As shown in Table 1, We select 5 social networks [5, 37] with attributes to verify the proposed algorithm’s feasibility. Where V represents the number of nodes in the network. E represents the number of edges. $|P|$ represents the number of attribute features. $\bar{d}$ represents the average degree, and $|C|$ represents the number of known communities.

The Facebook data set comes from the social lists of Facebook users who participated in the survey, containing each surveyor and their corresponding circle of friends. On average, there are 22 users in each social circle, and each user has 26 types of attributes, such as residence, birthday, colleagues, political leanings, etc., and these data are all anonymized. The Cora and PubMed data sets are citation networks, where nodes represent paper id, edges represent the relationship between the papers and the application, and the attributes of nodes are keywords that frequently appear in the paper. The Cornell data set comes from the university’s official website, where nodes represent web pages, edges are hyperlinks existing in web pages, and node attributes are keywords frequently appearing in web pages. DBLP is a co-authored network. Nodes and edges represent the cooperative relationship between authors and authors, respectively. Edge weight is the number of jointly published papers, and the attribute of nodes is the keyword with high frequency in the paper.

The selected data sets are derived from public data sets of social network applications. These data sets collect the active status of some users over a period of time and do not represent all users. These data sets are mainly used to evaluate the feasibility of community discovery algorithms. The selected data sets contain the attributes of users. According to users who have similar interests but no social connection may come from the same community, we integrate the attributes of users to improve the accuracy of community division.

5.2 Evaluation index

We use the following three evaluation methods to verify the feasibility of the proposed algorithm from different perspectives:

Definition 7: (extended modularity function, $Q$ ). The modularity proposed by Newman et al. has become an important indicator for evaluating non-overlapping communities [38], but it is not suitable for overlapping communities. Therefore, Shen et al. [39] proposed the extended module degree function. $Q$ is defined as

$\displaystyle Q=\frac{1}{2m}\sum\limits_{i=1}^{k}{\sum\limits_{p,q\in C_{i}}{% \frac{\left[A_{pq}-\frac{d_{p}d_{q}}{2m}\right]}{Q_{p}Q_{q}}}}$ (8)

Where $k$ is the number of communities in the network. $Q_{p}$ and $Q_{q}$ are the number of nodes in the communities to which nodes $p$ and $q$ belong, respectively. $A_{pq}$ is the weight between the node $p$ and $q$ . If $p$ and $q$ have edges, the value of $A_{pq}$ is the weight, otherwise, it is 0. When the network is not a weighted graph, the weight is 1. $m$ is the sum of the weights of all edges in the network, $d_{p}=\sum\limits_{q}{A_{pq}}$ is the sum of the weights of all the edges connected to the node $p$ , and $\frac{d_{p}d_{q}}{2m}$ is the possibility that the nodes $p$ and $q$ are connected in a random state. The larger the $Q$ value, the closer the nodes in the community are connected, and the sparser the connections between communities, which indicates that the community division is more accurate.

Definition 8: (Normalized Mutual Information, NMI) [40] NMI is used to compare the difference between the actual community and the community obtained by applying an algorithm. NMI is expressed as:

$\displaystyle\textit{NMI}(T,F)=\frac{-2\sum\limits_{i=1}^{C_{T}}{\sum\limits_{% j=1}^{C_{f}}{N_{ij}\log(N_{ij}V/N_{i.}N_{.j})}}}{\sqrt{\sum\limits_{i=1}^{C_{T% }}{N_{i.}\log(N_{i.}/N)}\sum\limits_{j=1}^{C_{F}}{N_{.j}\log(N_{.j}/N)}}}$ (9)

Where $V$ is the number of nodes, $N$ is the confusion matrix, and the element $N_{ij}$ in the matrix represents the number of nodes jointly owned by the real community $i$ and the discovered community $j$ . $C_{T}$ and $C_{F}$ are the number of real communities and discovered communities, respectively. $N_{i.}$ and $N_{.j}$ are the sum of the elements in the $i$ -th row and $j$ -th column of the matrix $N$ , respectively. The value range of NMI is [0, 1]. The closer the NMI is to 1, the closer the divided community is to the real community.

Definition 9: (F-score) [22]F-score is a comprehensive measure of Accuracy and Recall. $F$ -score is defined as.

$\displaystyle\textit{F-score}=\frac{2\ast\textit{precision}\ast\textit{recall}% }{\textit{precision}+\textit{recall}}$ (10)

Where $\textit{precision}=\frac{{1}}{I}\sum\limits_{i=1}^{I}{\frac{|c_{i}\cap g_{i}|}% {|c_{i}|}}$ , $\textit{recall}=\frac{{1}}{I}\sum\limits_{i=1}^{I}{\frac{|c_{i}\cap g_{i}|}{|g% _{i}|}}$ . $I$ is the number of communities. $g_{i}$ and $c_{i}$ are respectively the community discovered by the algorithm and the real community. The closer the F-score value is to 1, the closer the community discovered by the algorithm is to the real community.

5.3 Results and parameter analysis

5.3.1 Parameter analysis

The parameter $T_{1}$ is the clustering radius, which determines the number of nodes owned by the current community. The larger the value $T_{1}$ , the larger the coverage of the current community in the entire network. The parameter $T_{2}$ is the community’s fusion threshold, and communities that satisfy a certain threshold can be merged. In this article, we determine the values of parameters $T_{1}$ and $T_{2}$ through the following experimental design. We divide the parameter $T_{2}$ into 10 equal parts and conduct a total of 9 experiments. The value of the parameter $T_{2}$ is different for each experiment. During the experiment, the parameter $T_{2}$ remains unchanged. With the gradual increase of $T_{1}$ , by observing the degree of change of the evaluation index NMI in each data set, we determine the final value of each parameter.

Figure 4.

The value of NMI under different parameters.

It can be seen from Fig. 4 that the NMI value of the proposed algorithm has different changing trends in different data sets. In the DBLP and Facebook datasets, because the number of known communities and the degree of overlap between communities is greater, a larger fusion threshold makes the algorithm performs better. On the contrary, in the Cora, PubMed, and Cornell data sets, because the number of known communities and the degree of overlap between communities are small, the smaller the fusion threshold makes the algorithm performance improve. As the parameter $T_{1}$ increases, the NMI value image shows a parabolic trend. when $T_{1}\in[0.3,0.4]$ , the value of NMI reaches the maximum amount. It shows that in different data sets, the effect of the clustering radius $T_{1}$ on the performance of the algorithm will not change with the change of the data set. Therefore, this paper recommends that for data sets with a large degree of overlap, the value range of the fusion parameter $T_{2}$ is [0.3–0.4]. For data sets with a small degree of overlap, the value range of the fusion parameter $T_{2}$ is above 0.7. The value range of the clustering radius $T_{1}$ is relatively stable, and the value is [0.3–0.4].

The parameter $\tau$ determines the range of community $C_{v}$ and indirectly determines the number of neighbors of the core node. To determine the value of the parameter $\tau$ , we designed the following experiment. We randomly select any node in the known community of a given data set and obtain the community where the node is located according to the proposed algorithm. I evaluate the quality of the community by using NMI to observe the change of the parameter $\tau$ . In each data set, we conducted 50 experiments, and the final results were averaged. The experimental results are shown in Fig. 5.

Figure 5.

The value of parameter $\tau$ .

It can be seen from the figure that in addition to the Core data set, in the other four data sets, when the value of $\tau$ is concentrated at 0.6, the NMI value is the highest. In the Core data set, the NMI value is the highest when the value is concentrated at 0.7. Without loss of generality, we choose the average value as the value of $\tau$ , and $\tau=$ 0.6.

5.3.2 Algorithm performance comparison

In this paper, to verify the feasibility of the proposed algorithm, we choose five classic algorithms and the proposed algorithm for experimental comparison. The algorithms are the LFM algorithm [15], the CFLEM algorithm [19], and the LOC algorithm [18] based on node structure characteristics, and the Tsoca-SA algorithm [21] and LocTAC [24] algorithm that merge node attribute characteristics. As a classic local optimization overlapping community discovery algorithm, the LFM algorithm has become the most referenced algorithm for comparison, analysis, and learning by related researchers due to its easy-to-understand principle and simple implementation. The CFLEM algorithm selects unvisited nodes with large clustering coefficients as core nodes, reducing the uncertainty of the results caused by randomly selecting core nodes. The LOC algorithm expands the community by adding the node with the greatest fitness and all k-factions where the node is located, which improves the expansion efficiency but affects the accuracy. The LocTAC algorithm integrates the structural characteristics and attribute characteristics of nodes, and uses local information to obtain the community structure by calculating the correlation between the core node and adjacent nodes, which improves the quality of community division. Unlike LocTAC, Tsoca-SA algorithm obtains overlapping community structure by using global network information. Therefore, this paper selects the above five algorithms as experimental references.

Table 2 shows the value of the evaluation index of each algorithm on different data sets. It can be seen from the table that the community quality obtained by the Tsoca-SA and LocTAC algorithms that integrate node structure and attribute information is significantly better than the LFM, CFLEM, and LOC algorithms based on node structure characteristics. Simultaneously, the proposed algorithm (OCBLIM) is generally better than other algorithms in three evaluation indicators. Since we convert the complex network structure in the social network into a simple distance measurement between nodes through the local interaction model, the community structure is obtained through the traditional clustering method. The free-riding problem of local optimization methods is avoided, and the quality and accuracy of the community are improved.

Table 2
Performance comparison of different algorithms

Dataset	Evaluation index	LFM	CFLEM	LOC	Tsoca-SA	LocTAC	OCBLIM
Facebook	$Q$	0.676	0.638	0.653	0.679	0.683	0.723
	NMI	0.646	0.621	0.658	0.703	0.731	0.755
	F-score	0.600	0.646	0.682	0.715	0.716	0.781
Cora	$Q$	0.653	0.639	0.621	0.673	0.651	0.694
	NMI	0.621	0.648	0.683	0.709	0.712	0.730
	F-score	0.642	0.633	0.650	0.691	0.705	0.701
PubMed	$Q$	0.608	0.614	0.602	0.632	0.651	0.720
	NMI	0.681	0.704	0.711	0.726	0.735	0.763
	F-score	0.647	0.645	0.694	0.726	0.731	0.786
Cornell	$Q$	0.607	0.612	0.603	0.619	0.624	0.699
	NMI	0.640	0.662	0.671	0.694	0.689	0.748
	F-score	0.670	0.684	0.706	0.736	0.722	0.794
DBLP	$Q$	0.672	0.661	0.678	0.708	0.680	0.704
	NMI	0.682	0.675	0.709	0.715	0.739	0.752
	F-score	0.671	0.698	0.711	0.731	0.741	0.782

Table 3

The $p$ -value of T-test between each comparison algorithm and OCBLIM algorithm in three evaluation indicators

Evaluation index	OCBLIM & LFM	OCBLIM & CFLEM	OCBLIM & LOC	OCBLIM & Tsoca-SA	OCBLIM & LocTAC
$Q$	0.004	0.000	0.010	0.029	0.004
NMI	0.000	0.000	0.010	0.010	0.030
F-score	0.000	0.001	0.004	0.0320	0.036

Figure 6.

Performance comparison of community $C_{v}$ in different data sets.

In order to verify the difference between OCBLIM algorithm and the compared algorithm, we conducted T-test analysis on each comparison algorithm and OCBLIM algorithm respectively. Without distinguishing data sets, we conducted T-test analysis for each evaluation indicator. As can be seen from Table 3, the $p$ -values of the three evaluation indexes are all less than 0.05, indicating that there are significant differences between OCBLIM and other comparison algorithms, and further indicating that the quality of communities divided by OCBLIM algorithm is better.

5.3.3 Performance analysis of community

C_{v}

To verify the given condition of any node $v\in V$ , the proposed algorithm gets the quality of community $C_{v}$ where node $v$ is located. We divide each original data set into two parts: the data set containing node structure and attribute characteristics, and the data set containing node structure characteristics only. We randomly select any node in the known community and obtain the community where the node is located according to the proposed algorithm. We use NMI to evaluate the quality of the community. In each data set, we conduct 50 experiments on each part, and the final results are averaged. As shown in Fig. 6, in each data set, The result of community division of datasets containing structural and attribute features is significantly higher than that of datasets containing only structural features. However, compared with previous communities, since a given node is randomly selected during the experiment, and the number of neighbors of the core node or the attribute feature frequency of the core node is greater than that of the non-core node, the quality of the obtained community is lower. But overall, the community quality of the fusion attribute data set is higher than 0.6, which meets the community classification standard [38]. The experimental results further verify the feasibility and $C_{v}$ versatility of the algorithm.

6. Summary and conclusions

Aiming at the existing problems of the traditional local optimization algorithm, we merge the node attribute characteristics and propose an overlapping community discovery algorithm based on the local interaction model (OCBLIM). We first obtain the core nodes of the network according to the proposed ICDP algorithm. Then, the local interaction model of the core node is established, and the interaction strength or the number of common attributes between the nodes in the network is converted into the change of the distance between the nodes. Finally, we obtain the overlapping community structure of social networks through the proposed CI algorithm. Experimental results on real data sets show that the community structure quality obtained by our proposed algorithm is generally better than other similar algorithms. In future work, to provide users with more humane community services, we propose a general framework for community discovery algorithms, which combines various complex information generated by users in real life.

Footnotes

Acknowledgments

This work was supported by the National Natural Science Foundation of China (61967013). This work was also supported by Northwest Normal University Graduate Research Funding Project (2020).

References

Žalik

K.R.

and Žalik

, Memetic algorithm using node entropy and partition entropy for community detection in networks, Information Sciences 445–446 (2018), 38–49.

Sánchez-Oro

and Duarte

, Iterated greedy algorithm for performing community detection in social networks, Future Generation Computer Systems 88 (2018), 785–791.

Cheng

Cui

Niu

and Zhang

, A local information based multiobjective evolutionary algorithm for community detection in complex networks, Applied Soft Computing 69 (2018), 357–367.

Zhou

Feng

and Zhao

, A novel community detection method in bipartite networks, Physica A 492 (2018), 1679–1693.

Zhang

Wang

Liu

Huang

and Wang

, A central edge selection based overlapping community detection algorithm for the detection of overlapping structures in protein-protein interaction networks, Molecules 23(10) (2018), 2633.

Tripathi

Parthasarathy

Sinha

Raman

and Ravindran

, Adapting community detection algorithms for disease module identification in heterogeneous biological networks, Frontiers in Genetics 10 (2019), 164.

Ding

Zhang

and Yang

, Node-community membership diversifies community structures: An overlapping community detection algorithm based on local expansion and boundary re-checking, Knowledge-Based Systems 198 (2020), 105935.

Palla

Derenyi

Farkas

and Vicsek

, Uncovering the overlapping community structure of complex networks in nature and society, Nature 435 (2005), 814–818.

Wen

Chen

Lin

Zhang

Yin

and Zhang

, A maximal clique based multiobjective evolutionary algorithm for overlapping community detection, IEEE Transactions on Evolutionary Computation 21(3) (2017), 363–377.

10.

Ahn

Bagrow

J.P.

and Lehmann

, Link communities reveal multiscale complexity in networks, Nature 466(7307) (2010), 761–764.

11.

Deng

Dong

and Ota

, Finding overlapping communities based on markov chain and link clustering, Peer-to-peer Networking and Applications 10(2) (2017), 411–420.

12.

Zhang

and Kang

, LPANNI: Overlapping community detection using label propagation in large-scale complex networks, IEEE Transactions on Knowledge and Data Engineering 31(9) (2019), 1736–1749.

13.

Luo

Zhu

and Ding

, Local community detection by the nearest nodes with greater centrality, Information Sciences 517 (2020), 377–392.

14.

Shi

Wang

Zhao

and Zhang

, Research status of community detection based on local expansion, Journal on Communications 40(1) (2019), 149–162.

15.

Lancichinetti

Fortunato

and Kertesz

, Detecting the overlapping and hierarchical community structure in complex networks, New Journal of Physics 11(3) (2009).

16.

Coscia

Rossetti

Giannotti

and Pedreschi

, Demon: a local first discovery method for overlapping communities, in: Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2012, pp. 615–623.

17.

Lee

Reid

Mcdaid

and Hurley

, Detecting highly overlapping community structure by greedy clique expansion, Proceedings of the knowledge discovery and data mining, 2010.

18.

and Fan

, Local optimization for clique-based overlapping community detection in complex networks, IEEE Access 8 (2020), 5091–5103.

19.

Yang

and Wang

, An overlapping community detection algorithm based on local expansion optimization, Computer Engineering & Science 40(12) (2018), 2258–2264.

20.

Jin

and Zhang

, Robust local community detection: On free-rider effect and its elimination, Proceedings of the VLDB Endowment 8(7) (2015), 798–809.

21.

Zhang

Jiang

and Xie

, A Two-Stage Overlapping Community Detection Based on Structure and Node Attributes in Online Social Networks, in: Proceedings of the International Joint Conference on Artificial Intelligence, 2019, pp. 310–320.

22.

and Liu

, An overlapping multiway spectral community detection method for the attributed network, Computer Engineering & Science 42(06) (2020), 984–992.

23.

Fang

Cheng

Luo

and Hu

, Effective community search over large spatial graphs, Proceedings of the VLDB Endowment 10(02) (2017), 709–720.

24.

Huang

and Lakshmanan

L.V.S.

, Attribute-driven community search, Proceedings of the VLDB Endowment 10(9) (2017), 949–960.

25.

Wala

Yahia

and Saoud

, Hybrid community detection approach in multilayer social network: Scientific collaboration recommendation case study, AICCSA, 2016, 1–8.

26.

Rodriguez

and Laio

, Clustering by fast search and find of density peaks, Science 344(6191) (2014), 1492–1496.

27.

Bai

Yang

and Shi

, An overlapping community detection algorithm based on density peaks, Neurocomputing, 2017, 7–15.

28.

Zhang

Chen

and Feng

. Overlapping community detection method based on rough sets and density peaks, Computer Science 47(05) (2020), 72–78.

29.

McCallum

Nigam

and Ungar

L.H.

, Efficient clustering of high-dimensional data sets with application to reference matching, in: Proceedings of the 6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2000, pp. 169–178.

30.

Sun

Jia

Huang

Wang

and Huang

, Distance dynamics based overlapping semantic community detection for node-attributed networks, Computational Intelligence 37 (2021), 678–700.

31.

Tang

Cao

Chen

and Lin

, A fast local community detection algorithm in complex networks, World Wide Web 24 (2021), 1929–1955.

32.

Whang

J.J.

Gleich

D.F.

and Dhillon

I.S.

, Overlapping community detection using neighborhood-inflated seed expansion, IEEE Transactions on Knowledge and Data Engineering 28(5) (2016), 1272–1284.

33.

Tabarzad

M.A.

and Hamzeh

, A heuristic local community detection method (HLCD), Applied Intelligence 46 (2017), 62–78.

34.

and Su

, Density peaks clustering by automatic determination of cluster centers, Journal of Frontiers of Computer Science and Technology 10(11) (2016), 1614–1622.

35.

Yang

Wang

and Zhou

, A clustering algorithm with adaptive cut-off distance and cluster centers, Data Analysis and Knowledge Discovery 2(3) (2018), 39–48.

36.

Zhang

Ding

and Yang

, Revealing the role of node similarity and community merging in community detection, Knowledge-Based Systems 165 (2019), 407–419.

37.

Zhang

Chen

Wang

Bai

and Hancock

E.R.

, Depth-based subgraph convolutional auto-encoder for network representation learning, Pattern Recognition 90 (2019), 363–376.

38.

Newman

M.E.J.

and Girvan

, Finding and evaluating community structure in networks, Physical Review E 69(2) (2004), 026113–026113.

39.

Shen

Cheng

and Cai

, Detect overlapping and hierarchical community structure in networks, Physica A-statistical Mechanics and Its Applications 388(8) (2009), 1706–1712.

40.

, Leader-based community detection algorithm in attributed networks, IEEE Access 9 (2021), 119666–119674.

The overlapping community discovery algorithm based on the local interaction model

Abstract

Keywords

1. Introduction

2. Related technologies

2.1 Social networks

2.2.1 Clustering by Fast Search and find of density peaks

2.2.2 Canopy clustering

3. Key technology

3.1 Community definition

4. Overlapping community discovery algorithm based on the local interaction model

4.2.1 Local interaction model

4.3 Algorithm description

5. Experimental analysis

5.1 Data set

Table 1 Data set

5.3.1 Parameter analysis

Table 2 Performance comparison of different algorithms

6. Summary and conclusions

Footnotes

Acknowledgments

References

Table 1
Data set

Table 2
Performance comparison of different algorithms