# Multilayer Social Network Overlapping Community Detection Algorithm Based on Trust Relationship

Authors: Junjie Jia; Pengtao Liu; Xiaojin Du; Yuchao Zhang
Journal: Wireless Communications and Mobile Computing
 (2021)

---

## Abstract

Aiming at the problem of the lack of user social attribute characteristics in the process of dividing overlapping communities in multilayer social networks, in this paper, we propose a multilayer social network overlapping community detection algorithm based on trust relationship. By combining structural trust and social attribute trust, we transform a complex multilayer social network into a single-layer trust network. We obtain the community structure according to the community discovery algorithm based on trust value and merge communities with higher overlap. The experimental comparison and analysis are carried out on the synthetic network and the real network, respectively. The experimental results show that the proposed algorithm has higher harmonic mean and modularity than other algorithms of the same type.


---

## Body

## 1. Introduction

As a representation model of user interaction, a social network is often used to analyze the complex social structure between people in real life. A social network is composed of a set of nodes and an edge set, where nodes represent users and edges represent interactions between users [1]. According to different types of interactions, different social network structures are formed. In recent years, a large number of social network applications have gradually catered to the needs of people in all aspects of daily life and have developed towards more humane, daily and intelligent aspects, such as Weibo, Twitter, and Facebook. According to research, more than 80% of users use at least one social network application [2]. Users use social network applications as a platform to post their emotions, attitudes, and values to their circle of friends. They can forward, comment, and like each other. As a result, various complex social relationship data are generated. Since different social platforms correspond to different social relationships, it is obviously not advisable to adopt a traditional single-layer social network to establish a user interaction model. Therefore, multilayer social networks are proposed to represent the complex network of relationships between people in the real world. In a multilayer social network, the nodes are users, and each layer represents a type of user’s social relationship [3–5].Community detection, as an important tool for analyzing and understanding multilayered social networks, is manifested in close connections between nodes in the same community and sparse connections between different communities. It is widely used in various aspects of real life, such as public opinion detection [6], recommendation systems [7], and epidemic spread [8], and has become one of the key technologies for understanding and analyzing the structure of multilayer social networks. As shown in Figure 1(b), the research network consists of three layers: coauthoring layer, Twitter, and Facebook. At the coauthoring layer, if the authors have copublished papers, the nodes are connected to each other. In the Twitter and Facebook layers, the connection between nodes corresponds to the interaction between users. As shown in Figure 1(c), its community is a group of researchers with the same research direction. Through community discovery, users in the same community communicate with each other, answer questions, and recommend papers to better serve scientific research [9]. For a long time in the past, many scholars mainly focused on the structural relationship of nodes in the network, that is, the association relationship between users, to detect nonoverlapping communities [10]. However, related studies have shown [11] that communities in the real world are not separated. For example, users have multiple roles in social networks and can be in multiple communities at the same time; that is, communities can overlap. Faced with such a complex multilayer social network, detecting overlapping communities has become a hot topic in the current research.Figure 1
Schematic diagram of multilayer social network. (a) Multilayer social network (the research network), (b) social relations at every level, and (c) community structure.Currently, relevant researchers apply most overlapping community detection algorithms to single-layer social networks: for example, local optimization community detection algorithm [12, 13], improved label propagation community detection algorithm [14], and parallel multiobjective optimization community detection algorithm [15]. In addition, it also includes a nonnegative matrix factorization community detection algorithm [16]. Experimental results show that these algorithms have achieved good results in single-layer networks. However, a multilayer social network consists of multiple layers, and each layer corresponds to a social relationship between users. It can be seen that these algorithms cannot be directly adapted to multilayer networks. For this reason, many researchers adopt the most direct strategy to extend the single-layer overlapping community discovery method to multiple layers [17] or use a multiobjective optimization method [18] to divide communities. However, these methods show lower performance when the network is large.In addition, some researchers are inspired by user interaction behavior in social networks to simulate social interaction by constructing trust between users and divide communities based on the trust relationship between users. Users with a stronger trust relationship establish similar interests and hobbies through mutual influence and finally form a relatively stable group [19]. Compared with other community division methods, the trust-based community division method is simple in principle and has strong practical significance. At the same time, the experimental results show that the trust-based community discovery method greatly improves the accuracy of community detection [20, 21]. However, for multilayer social networks, these methods can only obtain nonoverlapping communities of the network, and in the process of building trust, they rely excessively on the structural characteristics of the network and ignore the characteristics of social attributes. Structure and social attributes are the basic characteristics of the network. The structural characteristics describe the user’s social scope, while the social attributes are the inherent characteristics of the user and correspond to the user’s social style.Based on this, in this paper, we propose a multilayer social network overlapping community detection algorithm based on trust relationship (MOCBT). We integrate the characteristics of social attributes and transform the complex social information in the multilayer social network into a single-layer network based on trust value. We divide the community by using the local information of the network, thereby improving the accuracy of community detection.The main contributions of this article are summarized as follows:(1)
By integrating the characteristics of social attributes, we propose an evaluation model for evaluating the strength of trust between users(2)
Based on the trust relationship between nodes, we propose a community detection algorithm based on trust value(3)
We propose a multilayer network overlapping community detection algorithm based on trust relationship (MOCBT), which provides a general framework for multilayer network community discovery based on trust relationship. Experimental results show that the MOCBT algorithm is better than other community detection algorithms of the same type as a wholeThe structure of the rest of the article is as follows: Section2 summarizes the research status and the existing problems of multilayer social network community detection. Section 3 introduces the relevant theories of community detection. Section 4 discusses the proposed algorithm in detail. Section 5 verifies the feasibility of the proposed algorithm through experimental analysis. Section 6 summarizes the full text and indicates the work to be done in the next step.


## 2. Related Work

Recalling the traditional community detection methods in multilayer social networks can be divided into two main strategies: single-layer community expansion and integration methods and other methods. The first strategy extends the single-layer network community detection algorithm to multilayer networks. Rodriguez [22] proposed a multilayer network community detection algorithm framework based on path algebra. They use tensors to represent multilayer networks and slice bidirectionally to generate a single relational path matrix. Chen et al. [23] fused the multilayer network into a weighted single-layer network by calculating the similarity between nodes and used an improved label propagation algorithm to obtain the community. However, these methods will cause the lack of network information in the process of integration and expansion, resulting in inaccurate community detection [24]. Besides, Ma et al. [24] proposed a semisupervised nonnegative matrix factorization algorithm for multilayer networks, by obtaining denser communities in the network in advance. Gao et al. [25] proposed a community detection model suitable for complex networks by combining a competitive learning mechanism and random deterministic roles. However, the communities obtained by the above algorithm are nonoverlapping. To this end, Tehrani and Magnani [17] used the first strategy to redefine the definition of faction filtering algorithms and proposed an extensible faction filtering overlapping community discovery algorithm. Based on the basic theory that users in the same community have dense connections and users in different communities have sparse connections, Shahmoradi et al. [18] obtained network overlapping communities by using multiobjective optimization. However, these methods only use the structural characteristics of the network in the process of community detection, and the divided communities are not ideal when the data scale is large.As we all know, social networks are composed of users and the interaction between users, but the interaction between users is ultimately a trust relationship between each other. Based on this, Chen et al. [26] established a trust model by integrating direct trust and indirect trust between users. They proposed a single-layer social network-oriented nonoverlapping community discovery algorithm by combining edge fitness and community fitness. Ding et al. [27] established a trust evaluation model between users by integrating structural similarity and neighbor similarity and then obtained overlapping communities of single-layer networks by using coarse-grained K-medoids. In contrast, Li et al. [28] established a trust model between users by analyzing the homogeneity between nodes and the shortest path and proposed a multilayer network local community discovery algorithm based on trust relationships. However, in the process of establishing a trust model, these algorithms essentially only use the structural features of the network, ignoring the social attributes of the network. Therefore, for multilayer social networks, it is necessary to design an overlapping community discovery algorithm based on trust relationships and integrating social attribute characteristics.


## 3. Related Theories

### 3.1. Multilayer Social Network

The user information we collect and extract is usually expressed as unstructured. To facilitate analysis and understanding, we use the ontology model [29] to structure the user’s social information. The ontology model can be used as a standard modeling tool, while also ensuring interoperability between data.After the data is structured, we define a multilayer social network as an undirected graphG=V,E,P,L with attribute information.L=Lii=1,⋯,s represents the number of network layers. V=vii=1,⋯,n represents the set of n nodes in the graph. E=vi,vj,ωvi,vj∈Vs.t.E=m represents the set of m edges in the graph. The edges represent the social relationships between nodes, and the social relationships at different levels are different. The edge weight ω represents the strength of the relationship between the nodes. P=p1,⋯,pk represents the set of attributes of nodes in the network.


### 3.2. Community

We collected descriptions of communities from previous literature [7–18], which can be summarized as follows:(i)
Nature 1: the nodes within the community are closely connected, and the nodes within the community are sparsely connected with nodes outside the community.It can be seen that the definition of community in the past literature focuses on the structural characteristics of the network. However, this is not the case. Users with close structural relationships but different social attributes may not necessarily join the same community. This is mainly determined by the user’s social status and value; that is, birds of a feather flock together. Structural characteristics and social attribute characteristics are the two basic attributes of the network. Social attribute characteristics include two aspects of personal status and value. Personal status refers to demographic characteristics, such as race, gender, age, education level, and occupation. Personal value refers to thoughts, attitudes, lifestyles, etc.(ii)
Nature 2: structural features are only the prerequisites for the formation of communities, and what really matters is the characteristics of social attributes. In other words, nodes within the community are closely connected and have similar social attribute characteristics, while nodes with different social attribute characteristics and close connections may not be in the same community.


### 3.3. Degree of Community Overlap

When there are many common nodes between two communities, it means that they can be merged.Definition 1 (degree of community overlap,β) [19].
β is used to judge whether the communities can be merged. When β is higher, it means that the communities can be merged.(1)β=Ci∩CjminCi,Cj.Ci∩Cj represents the number of nodes shared by communities Ci and Cj, and minCi,Cj represents the minimum number of nodes owned by communities Ci and Cj.


### 3.4. Problem Description

Trust, as the core part of social interaction, is a concentrated expression of a person’s mode of getting along in social networks, and it is also a bridge to maintain and establish interpersonal relationships. By building trust, people maintain a long-term and stable social connection. As time changes, users with stronger trust relationships gather together and share information with each other. Through mutual influence, similar interests and hobbies are established, and finally a relatively stable group is formed [19]. It can be seen that the strength of the trust relationship between users is the main factor that affects the formation of the community structure. Based on this relationship, in this article, we transform the complex information between users in a multilayer network into a trust relationship. After that, we proposed an overlapping community discovery algorithm based on trust relationship, which provides a new idea for the division of overlapping communities in multilayer social networks.


## 3.1. Multilayer Social Network

The user information we collect and extract is usually expressed as unstructured. To facilitate analysis and understanding, we use the ontology model [29] to structure the user’s social information. The ontology model can be used as a standard modeling tool, while also ensuring interoperability between data.After the data is structured, we define a multilayer social network as an undirected graphG=V,E,P,L with attribute information.L=Lii=1,⋯,s represents the number of network layers. V=vii=1,⋯,n represents the set of n nodes in the graph. E=vi,vj,ωvi,vj∈Vs.t.E=m represents the set of m edges in the graph. The edges represent the social relationships between nodes, and the social relationships at different levels are different. The edge weight ω represents the strength of the relationship between the nodes. P=p1,⋯,pk represents the set of attributes of nodes in the network.


## 3.2. Community

We collected descriptions of communities from previous literature [7–18], which can be summarized as follows:(i)
Nature 1: the nodes within the community are closely connected, and the nodes within the community are sparsely connected with nodes outside the community.It can be seen that the definition of community in the past literature focuses on the structural characteristics of the network. However, this is not the case. Users with close structural relationships but different social attributes may not necessarily join the same community. This is mainly determined by the user’s social status and value; that is, birds of a feather flock together. Structural characteristics and social attribute characteristics are the two basic attributes of the network. Social attribute characteristics include two aspects of personal status and value. Personal status refers to demographic characteristics, such as race, gender, age, education level, and occupation. Personal value refers to thoughts, attitudes, lifestyles, etc.(ii)
Nature 2: structural features are only the prerequisites for the formation of communities, and what really matters is the characteristics of social attributes. In other words, nodes within the community are closely connected and have similar social attribute characteristics, while nodes with different social attribute characteristics and close connections may not be in the same community.


## 3.3. Degree of Community Overlap

When there are many common nodes between two communities, it means that they can be merged.Definition 1 (degree of community overlap,β) [19].
β is used to judge whether the communities can be merged. When β is higher, it means that the communities can be merged.(1)β=Ci∩CjminCi,Cj.Ci∩Cj represents the number of nodes shared by communities Ci and Cj, and minCi,Cj represents the minimum number of nodes owned by communities Ci and Cj.


## 3.4. Problem Description

Trust, as the core part of social interaction, is a concentrated expression of a person’s mode of getting along in social networks, and it is also a bridge to maintain and establish interpersonal relationships. By building trust, people maintain a long-term and stable social connection. As time changes, users with stronger trust relationships gather together and share information with each other. Through mutual influence, similar interests and hobbies are established, and finally a relatively stable group is formed [19]. It can be seen that the strength of the trust relationship between users is the main factor that affects the formation of the community structure. Based on this relationship, in this article, we transform the complex information between users in a multilayer network into a trust relationship. After that, we proposed an overlapping community discovery algorithm based on trust relationship, which provides a new idea for the division of overlapping communities in multilayer social networks.


## 4. Algorithm Description

Aiming at the shortcomings of traditional community detection methods, in this article, we propose a multilayer network overlapping community detection algorithm based on trust relationships (MOCBT). By combining the social attribute characteristics of the network, we transform the complex information between nodes in the multilayer network into a single-layer network based on trust value. Based on the community detection algorithm of trust value, we obtain overlapping community structure.As shown in Figure2, our proposed community detection algorithm consists of three steps.(Step 1)
We combine node structure trust and social attribute trust to obtain a comprehensive trust value.(Step 2)
We convert the trust value between nodes into trust distance and obtain the core node set according to the trust factor and the minimum trust distance and then expand the nodes that meet the conditions to the community where the core node is located.(Step 3)
We merge communities with a high degree of overlap.Figure 2
Flow chart of MOCBT algorithm.


### 4.1. Establish Trust Value

In this section, we will describe in detail how to convert the complex information of nodes in a multilayer social network into a single-layer trust value. Since the structure and social attributes of nodes are the two basic characteristics of the network and trust value can be used to measure the intensity of interaction between user nodes in the network and the possibility of being in the same community, the structure and social attributes of nodes have become the main factors affecting trust.


#### 4.1.1. The Impact of Structure on Trust

Definition 2 (trust value of the single-layer shortest path,nvi,vj).
The longer the shortest path between user nodesvi and vj, the smaller the value of nvi,vj.In the field of communication, the longer the path the information travels, the weaker the accuracy and completeness of the information. Similarly, in one of the layers of a multilayer social network, when two user nodes need to establish an interactive relationship, the more nodes they pass, the lower the trust between them. For example, if users A and B have no direct interaction relationship, but both have a direct connection with user C; the trust between users A and C or B and C is stronger than the trust between users A and B.Definition 3 (trust value of the number of single-level paths,Dvi,vj).
The more paths between user nodesvi and vj, the greater the value of Dvi,vj.For example, users A and B are friends and have many friends in common, indicating that they have many common interests and show closeness.Definition 4 (multilayer structure trust value,D_trustvi,vj).
Given a multilayer social networkG=L,V,E,P, combined with Definitions 2 and 3, the multilayer structure trust value between nodes can be expressed as(2)D_trustvi,vj=∑Lωij×Dvi,vj×nvi,vj,where L represents the number of network layers and ωij represents the interaction weight, that is, the frequency of interaction between users. The larger the D_trustvi,vj, the higher the user’s trust.


#### 4.1.2. The Impact of Social Attributes on Trust

Structural features mainly exist in the form of edges in multilayer social networks, while social attribute features are attached to the network and are inherent characteristics of users. Research shows [30] that the higher the similarity of social attributes between nodes in social networks, the stronger the homogeneity between users, and homogeneity can be described as the degree of trust between users [27].Definition 5 (social attribute trust value,S_trustvi,vj).
Given a multilayer social networkG=L,V,E,P, the more social attributes shared between users, the stronger the social attribute trust value.(3)S_trustvi,vj=1P∑p1pk∑L1LsSpvi,vjλLp,where P represents the number of social attributes, λLp represents the weight of the attribute p in the L layer, and Spvi,vj represents the trust relationship between nodes vi and vj for the attributep. According to different types of attributes, the value of Spvi,vj can be divided into two situations. When the attribute p is a discrete attribute, such as occupation and diploma, if users vi and vj have the same attribute value, the value of Spvi,vj is 1; otherwise, it is 0. When the attribute p is the attribute of the text, such as search records and chat records, inspired by short text mining, we calculate the value of Spvi,vj based on the frequency of keywords in the text. Assuming that k,k=1,⋯,k is the keyword of the text attributep, then Spvi,vj=∑k=1kIuk×Ivk×1/lgDink.Where Dink represents the number of nodes containing the keyword k and Iuk represents whether the attribute of node u contains k, if it does, Iuk=1; otherwise, Iuk=0.


#### 4.1.3. Comprehensive Trust Value

Definition 6 (comprehensive trust value,trustvi,vj).
GivenG=L,V,E,P, D_trustvi,vj, and S_trustvi,vj, the comprehensive trust value of user vi to user vj can be expressed as(4)trustvi,vj=D_trustvi,vjD_trustvi×τvi,vj,where trustvi,vj represents the one-way trust value of user vi to vj. When the value of trustvi,vj is closer to 1, the trust relationship between user vi and vj is stronger. D_trustvi represents the sum of trust between user vi and its neighbor node. τvi,vj represents an indicator function. When S_trustvi,vj is less than or equal to 0, τvi,vj=0; on the contrary, τvi,vj=S_trustvi,vj.Affected by education, experience, and life background, the trust between users is not equivalent; that is, uservi’s trust for vj is not equivalent to user vj’s trust for vi. However, in the process of interaction, the establishment of a trust relationship between users often depends on the party with a lower trust value. For this reason, we choose mintrustvi,vj,trustvj,vi as the ultimate trust between users.


### 4.2. Discover the Community

In the previous section, we transformed the complex multilayer social network into a single-layer network based on trust value, which greatly simplified the scale of the problem. In this section, we abstract the transformed single-layer trust network into a data domain based on the data field theory [27], where the data points represent users and the trust value is expressed as the distance between the data points, that is, the interaction strength of the nodes. In view of the network’s small-world effect, scale-free nature, and the aggregation characteristics of the network node structure, the core nodes in the community often have strong local interactions. That is, the core node has strong interaction with neighbor nodes, but the interaction between core nodes in different communities is weak. We find the core node by calculating the trust factor and the minimum trust value, obtain the community where the core node is located according to the core value change rate, and propose a community discovery algorithm based on trust value (CAOT).Since the trust value between nodes decreases with the increase of the distance, we use the Gaussian function to objectively measure the changing trend of the trust value of the nodes with the distance.Definition 7 (trust distance,dvi,vj).
Given a multilayer social networkG=L,V,E,P, the trust distance of node vi∈V to node vj∈V is expressed as(5)dvi,vj=exptrustvi,vj2σ2.Definition 8 (trust factor,ρvi).
The trust factor is described as the sum of the trust value of nodevi and its neighbor node Γvi. The trust factor ρvi of node vi is expressed as(6)ρvi=∑vj∈Γvitrustvi,vj.Definition 9 (minimum trust distance,δvi).
Due to the large trust distance between core nodes in different communities,δvi is described as the minimum trust distance from node vi to node vj with a higher trust factor. According to the value of the trust factor, δvi is divided into two types of values, defined as(7)δvi=maxvj∈Vdvi,vj,ifρvi=maxρvi,minvj:ρvj>ρvidvi,vj,otherwise.
When the trust factorρvi of the node vi is the largest, δvi is the maximum value of dvi,vj of node vi and other nodes vj. On the contrary, when the trust factor of node vi is not the maximum, δvi is the minimum value of dvi,vj of the node vi and other nodes vj, and the trust factor of node vj is greater than the trust factor of node vi.Since core nodes have a higher trust factor and a larger minimum trust distance than noncore nodes, we sort the core valueωvi=ρvi×δvi of each node in an ascending order. There is a clear downward trend from the core value of the core node to the core value of the noncore node. Therefore, we use the trend of slope change to automatically select the core node and define the trend as ratevi=i−1ωvi−1−ωvi/ωvi−ωvi+1, where i−1 is the weight value to prevent the rapid increase of ratevi, so as to improve the accuracy of core node selection. Finally, we denote the obtained core node set as H=hii=1,⋯,z.Definition 10 (the community where the core node is located,Chi).
Given the core nodehi∈H and the noncore node vj∈V−H, if dvj,hi<ε, then vj∈Chi.The thresholdε determines whether node vj can join community Chi. In order to determine the value of ε, we conducted a detailed experimental comparative analysis.The CAOT algorithm first uses the Gaussian function to objectively measure the trend of the trust valuetrustvi,vj between nodes with distance. By calculating the trust factor ρvi and trust distance δvi of each node, the algorithm automatically obtains the network core node set H. After that, the algorithm initializes the community set Ch where each core node is located and adds noncore nodes vj that meet the conditions to the current community. Finally, the community set where each core node is located is obtained, and the pseudocode of the algorithm is shown in Algorithm 1.Algorithm 1: CAOT algorithm.
Input: Multi-layer social network, G=V,E,P,L。Output: The community collection where the core node is located, ChCh=Chii=1,⋯,z1: Initialization,Chi=∅2:forviinV:3:forvjinV:4:dvi,vj=exptrustvi,vj/2σ25:endfor6:endfor7:forviinV:8:ωvi=ρvi×δvi9:endfor10:sortωvi11:According toratevi, the core node set H is obtained12:Chi=hi // We initialize the community where each core node is located, that is, the core node represents an initial community.13:forhiinCh:14:forvjinV−H:15:ifdvj,hi<ε16:Chi⟵vi //Node vi is added to community Chi.17:endif18:endfor19:endfor20:returnCh


### 4.3. Community Merger

When there are more public nodes in any two communities obtained by the above steps, the communities may have excessive overlap. Therefore, it is necessary for us to further process the obtained communities to reduce redundant communities and improve the quality of community discovery. In this paper, we use formula (1) to calculate β the degree of overlap between two communities to determine whether the communities can be integrated.


### 4.4. Algorithm Description

Aiming at the problem of the lack of social attribute characteristics when constructing user trust relationships in multilayer social networks, we integrate social attribute characteristics to propose a new way of representing user trust values. Combining the community discovery algorithm CAOT based on trust value, we propose a multilayer social network overlapping community discovery algorithm based on trust relationships (MOCBT). The proposed algorithm supports two or more layers of social networks. The input of the algorithm is a multilayer social networkG, and the output is a set of overlapping communities C. The algorithm first combines structure and attribute trust to obtain a comprehensive trust value trustvi,vj. After that, the community set Ch where the core node is located is obtained according to the CAOT algorithm. Finally, the communities with a higher degree of overlap are merged according to the fusion threshold γ. The algorithm steps are in Algorithm 2.Algorithm 2: MOCBT algorithm.
Input: Multi-layer social networkG=V,E,P,L.Output: Overlapping community setsCC=Cii=1,⋯,z.1: InitializationCi=∅2:forviinV:3:forvjinV:4:trustvi,vj5:endfor6:endfor7:trustvi,vj=mintrustvi,vj,trustvj,vi8: According to Algorithm1, we obtain the community set Ch where the core node is located.9:C=Ch10:forCiinC:11:forCjinC:12:ifCi∩Cj/min∣Ci,Cj∣>γ:13:Ci=Ci∩Cj14:endif15:endwhile16: ReturnC


### 4.5. Algorithm Complexity Analysis

In order to verify the practicability of the algorithm, we analyzed the time and space complexity of Algorithms1 and 2, respectively.


#### 4.5.1. Time Complexity

In a multilayer network,n represents the number of nodes, and z represents the number of core nodes. In Section 4.1, we establish the trust value between user nodes by traversing each node in the network, and the time complexity is On2. In Section 4.2, we first convert the trust between nodes in the network into distance, and the time complexity is On2. Then, we get the core value of each node, and the time complexity is On. We sort the core values to obtain core nodes, and the time complexity is Onlog2n. Finally, we obtain the community where each core node is located, and the time complexity is Oz×n−z. In Section 4.3, the time complexity of merging communities is Oz2. Therefore, the total time complexity of Algorithm 1 is On2. The time complexity of Algorithm 2 is On2.


#### 4.5.2. Space Complexity

Since we used the sorting method, the space complexity of Algorithms1 and 2 is O1 in the best case, and the space complexity is Onlog2n in the worst case.


## 4.1. Establish Trust Value

In this section, we will describe in detail how to convert the complex information of nodes in a multilayer social network into a single-layer trust value. Since the structure and social attributes of nodes are the two basic characteristics of the network and trust value can be used to measure the intensity of interaction between user nodes in the network and the possibility of being in the same community, the structure and social attributes of nodes have become the main factors affecting trust.


### 4.1.1. The Impact of Structure on Trust

Definition 2 (trust value of the single-layer shortest path,nvi,vj).
The longer the shortest path between user nodesvi and vj, the smaller the value of nvi,vj.In the field of communication, the longer the path the information travels, the weaker the accuracy and completeness of the information. Similarly, in one of the layers of a multilayer social network, when two user nodes need to establish an interactive relationship, the more nodes they pass, the lower the trust between them. For example, if users A and B have no direct interaction relationship, but both have a direct connection with user C; the trust between users A and C or B and C is stronger than the trust between users A and B.Definition 3 (trust value of the number of single-level paths,Dvi,vj).
The more paths between user nodesvi and vj, the greater the value of Dvi,vj.For example, users A and B are friends and have many friends in common, indicating that they have many common interests and show closeness.Definition 4 (multilayer structure trust value,D_trustvi,vj).
Given a multilayer social networkG=L,V,E,P, combined with Definitions 2 and 3, the multilayer structure trust value between nodes can be expressed as(2)D_trustvi,vj=∑Lωij×Dvi,vj×nvi,vj,where L represents the number of network layers and ωij represents the interaction weight, that is, the frequency of interaction between users. The larger the D_trustvi,vj, the higher the user’s trust.


### 4.1.2. The Impact of Social Attributes on Trust

Structural features mainly exist in the form of edges in multilayer social networks, while social attribute features are attached to the network and are inherent characteristics of users. Research shows [30] that the higher the similarity of social attributes between nodes in social networks, the stronger the homogeneity between users, and homogeneity can be described as the degree of trust between users [27].Definition 5 (social attribute trust value,S_trustvi,vj).
Given a multilayer social networkG=L,V,E,P, the more social attributes shared between users, the stronger the social attribute trust value.(3)S_trustvi,vj=1P∑p1pk∑L1LsSpvi,vjλLp,where P represents the number of social attributes, λLp represents the weight of the attribute p in the L layer, and Spvi,vj represents the trust relationship between nodes vi and vj for the attributep. According to different types of attributes, the value of Spvi,vj can be divided into two situations. When the attribute p is a discrete attribute, such as occupation and diploma, if users vi and vj have the same attribute value, the value of Spvi,vj is 1; otherwise, it is 0. When the attribute p is the attribute of the text, such as search records and chat records, inspired by short text mining, we calculate the value of Spvi,vj based on the frequency of keywords in the text. Assuming that k,k=1,⋯,k is the keyword of the text attributep, then Spvi,vj=∑k=1kIuk×Ivk×1/lgDink.Where Dink represents the number of nodes containing the keyword k and Iuk represents whether the attribute of node u contains k, if it does, Iuk=1; otherwise, Iuk=0.


### 4.1.3. Comprehensive Trust Value

Definition 6 (comprehensive trust value,trustvi,vj).
GivenG=L,V,E,P, D_trustvi,vj, and S_trustvi,vj, the comprehensive trust value of user vi to user vj can be expressed as(4)trustvi,vj=D_trustvi,vjD_trustvi×τvi,vj,where trustvi,vj represents the one-way trust value of user vi to vj. When the value of trustvi,vj is closer to 1, the trust relationship between user vi and vj is stronger. D_trustvi represents the sum of trust between user vi and its neighbor node. τvi,vj represents an indicator function. When S_trustvi,vj is less than or equal to 0, τvi,vj=0; on the contrary, τvi,vj=S_trustvi,vj.Affected by education, experience, and life background, the trust between users is not equivalent; that is, uservi’s trust for vj is not equivalent to user vj’s trust for vi. However, in the process of interaction, the establishment of a trust relationship between users often depends on the party with a lower trust value. For this reason, we choose mintrustvi,vj,trustvj,vi as the ultimate trust between users.


## 4.1.1. The Impact of Structure on Trust

Definition 2 (trust value of the single-layer shortest path,nvi,vj).
The longer the shortest path between user nodesvi and vj, the smaller the value of nvi,vj.In the field of communication, the longer the path the information travels, the weaker the accuracy and completeness of the information. Similarly, in one of the layers of a multilayer social network, when two user nodes need to establish an interactive relationship, the more nodes they pass, the lower the trust between them. For example, if users A and B have no direct interaction relationship, but both have a direct connection with user C; the trust between users A and C or B and C is stronger than the trust between users A and B.Definition 3 (trust value of the number of single-level paths,Dvi,vj).
The more paths between user nodesvi and vj, the greater the value of Dvi,vj.For example, users A and B are friends and have many friends in common, indicating that they have many common interests and show closeness.Definition 4 (multilayer structure trust value,D_trustvi,vj).
Given a multilayer social networkG=L,V,E,P, combined with Definitions 2 and 3, the multilayer structure trust value between nodes can be expressed as(2)D_trustvi,vj=∑Lωij×Dvi,vj×nvi,vj,where L represents the number of network layers and ωij represents the interaction weight, that is, the frequency of interaction between users. The larger the D_trustvi,vj, the higher the user’s trust.


## 4.1.2. The Impact of Social Attributes on Trust

Structural features mainly exist in the form of edges in multilayer social networks, while social attribute features are attached to the network and are inherent characteristics of users. Research shows [30] that the higher the similarity of social attributes between nodes in social networks, the stronger the homogeneity between users, and homogeneity can be described as the degree of trust between users [27].Definition 5 (social attribute trust value,S_trustvi,vj).
Given a multilayer social networkG=L,V,E,P, the more social attributes shared between users, the stronger the social attribute trust value.(3)S_trustvi,vj=1P∑p1pk∑L1LsSpvi,vjλLp,where P represents the number of social attributes, λLp represents the weight of the attribute p in the L layer, and Spvi,vj represents the trust relationship between nodes vi and vj for the attributep. According to different types of attributes, the value of Spvi,vj can be divided into two situations. When the attribute p is a discrete attribute, such as occupation and diploma, if users vi and vj have the same attribute value, the value of Spvi,vj is 1; otherwise, it is 0. When the attribute p is the attribute of the text, such as search records and chat records, inspired by short text mining, we calculate the value of Spvi,vj based on the frequency of keywords in the text. Assuming that k,k=1,⋯,k is the keyword of the text attributep, then Spvi,vj=∑k=1kIuk×Ivk×1/lgDink.Where Dink represents the number of nodes containing the keyword k and Iuk represents whether the attribute of node u contains k, if it does, Iuk=1; otherwise, Iuk=0.


## 4.1.3. Comprehensive Trust Value

Definition 6 (comprehensive trust value,trustvi,vj).
GivenG=L,V,E,P, D_trustvi,vj, and S_trustvi,vj, the comprehensive trust value of user vi to user vj can be expressed as(4)trustvi,vj=D_trustvi,vjD_trustvi×τvi,vj,where trustvi,vj represents the one-way trust value of user vi to vj. When the value of trustvi,vj is closer to 1, the trust relationship between user vi and vj is stronger. D_trustvi represents the sum of trust between user vi and its neighbor node. τvi,vj represents an indicator function. When S_trustvi,vj is less than or equal to 0, τvi,vj=0; on the contrary, τvi,vj=S_trustvi,vj.Affected by education, experience, and life background, the trust between users is not equivalent; that is, uservi’s trust for vj is not equivalent to user vj’s trust for vi. However, in the process of interaction, the establishment of a trust relationship between users often depends on the party with a lower trust value. For this reason, we choose mintrustvi,vj,trustvj,vi as the ultimate trust between users.


## 4.2. Discover the Community

In the previous section, we transformed the complex multilayer social network into a single-layer network based on trust value, which greatly simplified the scale of the problem. In this section, we abstract the transformed single-layer trust network into a data domain based on the data field theory [27], where the data points represent users and the trust value is expressed as the distance between the data points, that is, the interaction strength of the nodes. In view of the network’s small-world effect, scale-free nature, and the aggregation characteristics of the network node structure, the core nodes in the community often have strong local interactions. That is, the core node has strong interaction with neighbor nodes, but the interaction between core nodes in different communities is weak. We find the core node by calculating the trust factor and the minimum trust value, obtain the community where the core node is located according to the core value change rate, and propose a community discovery algorithm based on trust value (CAOT).Since the trust value between nodes decreases with the increase of the distance, we use the Gaussian function to objectively measure the changing trend of the trust value of the nodes with the distance.Definition 7 (trust distance,dvi,vj).
Given a multilayer social networkG=L,V,E,P, the trust distance of node vi∈V to node vj∈V is expressed as(5)dvi,vj=exptrustvi,vj2σ2.Definition 8 (trust factor,ρvi).
The trust factor is described as the sum of the trust value of nodevi and its neighbor node Γvi. The trust factor ρvi of node vi is expressed as(6)ρvi=∑vj∈Γvitrustvi,vj.Definition 9 (minimum trust distance,δvi).
Due to the large trust distance between core nodes in different communities,δvi is described as the minimum trust distance from node vi to node vj with a higher trust factor. According to the value of the trust factor, δvi is divided into two types of values, defined as(7)δvi=maxvj∈Vdvi,vj,ifρvi=maxρvi,minvj:ρvj>ρvidvi,vj,otherwise.
When the trust factorρvi of the node vi is the largest, δvi is the maximum value of dvi,vj of node vi and other nodes vj. On the contrary, when the trust factor of node vi is not the maximum, δvi is the minimum value of dvi,vj of the node vi and other nodes vj, and the trust factor of node vj is greater than the trust factor of node vi.Since core nodes have a higher trust factor and a larger minimum trust distance than noncore nodes, we sort the core valueωvi=ρvi×δvi of each node in an ascending order. There is a clear downward trend from the core value of the core node to the core value of the noncore node. Therefore, we use the trend of slope change to automatically select the core node and define the trend as ratevi=i−1ωvi−1−ωvi/ωvi−ωvi+1, where i−1 is the weight value to prevent the rapid increase of ratevi, so as to improve the accuracy of core node selection. Finally, we denote the obtained core node set as H=hii=1,⋯,z.Definition 10 (the community where the core node is located,Chi).
Given the core nodehi∈H and the noncore node vj∈V−H, if dvj,hi<ε, then vj∈Chi.The thresholdε determines whether node vj can join community Chi. In order to determine the value of ε, we conducted a detailed experimental comparative analysis.The CAOT algorithm first uses the Gaussian function to objectively measure the trend of the trust valuetrustvi,vj between nodes with distance. By calculating the trust factor ρvi and trust distance δvi of each node, the algorithm automatically obtains the network core node set H. After that, the algorithm initializes the community set Ch where each core node is located and adds noncore nodes vj that meet the conditions to the current community. Finally, the community set where each core node is located is obtained, and the pseudocode of the algorithm is shown in Algorithm 1.Algorithm 1: CAOT algorithm.
Input: Multi-layer social network, G=V,E,P,L。Output: The community collection where the core node is located, ChCh=Chii=1,⋯,z1: Initialization,Chi=∅2:forviinV:3:forvjinV:4:dvi,vj=exptrustvi,vj/2σ25:endfor6:endfor7:forviinV:8:ωvi=ρvi×δvi9:endfor10:sortωvi11:According toratevi, the core node set H is obtained12:Chi=hi // We initialize the community where each core node is located, that is, the core node represents an initial community.13:forhiinCh:14:forvjinV−H:15:ifdvj,hi<ε16:Chi⟵vi //Node vi is added to community Chi.17:endif18:endfor19:endfor20:returnCh


## 4.3. Community Merger

When there are more public nodes in any two communities obtained by the above steps, the communities may have excessive overlap. Therefore, it is necessary for us to further process the obtained communities to reduce redundant communities and improve the quality of community discovery. In this paper, we use formula (1) to calculate β the degree of overlap between two communities to determine whether the communities can be integrated.


## 4.4. Algorithm Description

Aiming at the problem of the lack of social attribute characteristics when constructing user trust relationships in multilayer social networks, we integrate social attribute characteristics to propose a new way of representing user trust values. Combining the community discovery algorithm CAOT based on trust value, we propose a multilayer social network overlapping community discovery algorithm based on trust relationships (MOCBT). The proposed algorithm supports two or more layers of social networks. The input of the algorithm is a multilayer social networkG, and the output is a set of overlapping communities C. The algorithm first combines structure and attribute trust to obtain a comprehensive trust value trustvi,vj. After that, the community set Ch where the core node is located is obtained according to the CAOT algorithm. Finally, the communities with a higher degree of overlap are merged according to the fusion threshold γ. The algorithm steps are in Algorithm 2.Algorithm 2: MOCBT algorithm.
Input: Multi-layer social networkG=V,E,P,L.Output: Overlapping community setsCC=Cii=1,⋯,z.1: InitializationCi=∅2:forviinV:3:forvjinV:4:trustvi,vj5:endfor6:endfor7:trustvi,vj=mintrustvi,vj,trustvj,vi8: According to Algorithm1, we obtain the community set Ch where the core node is located.9:C=Ch10:forCiinC:11:forCjinC:12:ifCi∩Cj/min∣Ci,Cj∣>γ:13:Ci=Ci∩Cj14:endif15:endwhile16: ReturnC


## 4.5. Algorithm Complexity Analysis

In order to verify the practicability of the algorithm, we analyzed the time and space complexity of Algorithms1 and 2, respectively.


### 4.5.1. Time Complexity

In a multilayer network,n represents the number of nodes, and z represents the number of core nodes. In Section 4.1, we establish the trust value between user nodes by traversing each node in the network, and the time complexity is On2. In Section 4.2, we first convert the trust between nodes in the network into distance, and the time complexity is On2. Then, we get the core value of each node, and the time complexity is On. We sort the core values to obtain core nodes, and the time complexity is Onlog2n. Finally, we obtain the community where each core node is located, and the time complexity is Oz×n−z. In Section 4.3, the time complexity of merging communities is Oz2. Therefore, the total time complexity of Algorithm 1 is On2. The time complexity of Algorithm 2 is On2.


### 4.5.2. Space Complexity

Since we used the sorting method, the space complexity of Algorithms1 and 2 is O1 in the best case, and the space complexity is Onlog2n in the worst case.


## 4.5.1. Time Complexity

In a multilayer network,n represents the number of nodes, and z represents the number of core nodes. In Section 4.1, we establish the trust value between user nodes by traversing each node in the network, and the time complexity is On2. In Section 4.2, we first convert the trust between nodes in the network into distance, and the time complexity is On2. Then, we get the core value of each node, and the time complexity is On. We sort the core values to obtain core nodes, and the time complexity is Onlog2n. Finally, we obtain the community where each core node is located, and the time complexity is Oz×n−z. In Section 4.3, the time complexity of merging communities is Oz2. Therefore, the total time complexity of Algorithm 1 is On2. The time complexity of Algorithm 2 is On2.


## 4.5.2. Space Complexity

Since we used the sorting method, the space complexity of Algorithms1 and 2 is O1 in the best case, and the space complexity is Onlog2n in the worst case.


## 5. Experimental Analysis

### 5.1. Data Set and Evaluation Indicators

We use the random model [31] to generate 8 multilayer synthetic social networks with different structure types according to the matching degree δ of the community and social attributes. The matching degree of the 8 synthetic networks is increased from 0.3 to 1. The matching degree is described as the similarity between the social attribute and the community theme set. In other words, when δ=0.3, it indicates that the probability of the user’s social attribute appearing in the community theme set is 0.3. The greater the probability, the higher the similarity. Each network is composed of 4 layers, and each layer adopts a different generation model. Each network is divided into two overlapping communities, including 100 nodes and 8 social attributes. As shown in Table 1, V represents the number of nodes and E represents the number of edges. P represents the number of social attribute features, and C represents the number of communities. L represents the number of network layers.Table 1
Synthetic data set.
Data setVEPCLδG11004008240.3G21004008240.4G31004008240.5G41004008240.6G51004008240.7G61004008240.8G71004008240.9G81004008241As shown in Table2, we use four real multilayer social network data sets [28], such as Twitter data set, QQ Zone data set, Remote Sensing, and Bio GRID. The Twitter data set contains various topics such as entertainment, science, and sports and is divided into three levels: mention, repost, and reply. The QQ Zone data set collects the user’s spatial data information, including the user’s age and gender. The data set is divided into three levels: posting, comment, and like. The Remote Sensing data set is a network structure derived from satellite remote sensing images and contains five levels. Bio GRID contains human genetic data and various protein interaction data and consists of seven layers. The way the proteins interact in each layer is different.(1)
Extended modularity,Q: since we considered the structure and attribute relationships of nodes, in order to measure the quality of overlapping communities, inspired by the literature [32], we rewrite the modularity as(8)Q=12m∑i=1∣C∣∑p,q∈CiApq−fpfq2mdp,hidq,hi,where C represents the number of communities in the network, Apq represents the weight between the node p and q, m represents the sum of the weights of all edges in the network, and fpfq/2m represents the possibility that the nodes p and q are connected in a random state. If the node p completely belongs to the community where the core node hi is located; then dp,hi=1. If node p does not completely belong to the community where core node hi is located, the value range of dp,hi satisfies 0<dp,hi<1. Otherwise, dp,hi=0.(2)
Harmonic mean value,F‐score [33]: F‐score is a comprehensive measure of precision and recall. The closer F‐score is to 1, the closer the community divided by the algorithm is to the real community(9)F‐score=2×precision×recallprecision+recall.Table 2
Real data set.
Data setVELTwitter4385379918543QQ zone56206280552363Bio GRID38,936342,5997Remote Sensing64243415


### 5.2. Experimental Results and Analysis

In order to verify the effectiveness of our proposed algorithm, the following five experiments are designed:(1)
By changing the value of parameterε, we observe the changes in the evaluation index in the synthetic data set to determine the appropriate value of ε(2)
We selected 11 representative community discovery algorithms to compare with the proposed algorithm to verify the community overlap performance of the proposed algorithm(3)
Through the analysis of the community detection results of the synthetic network and the real network, we verify the correctness of the proposed community nature(4)
In the synthetic network, we compare and analyze the proposed algorithm with the contrast algorithm(5)
In the real network, we compare and analyze the proposed algorithm with the contrast algorithmThroughout the experiment, according to a previous literature, we set the parameterσ=1.866. β reflects the degree of community overlap. The higher the value of β, the more nodes shared between communities. In order to reduce community redundancy, we set a fusion threshold γ. That is, when β>γ, it indicates that communities with many nodes in common can be merged into one community. The higher the value of γ, the smaller the number of final communities. In this article, we set γ=0.75 [27].


#### 5.2.1. The Value of Parameterε

In this section, we discuss the influence of parameterε on the proposed algorithm. In the 8 synthetic networks, we use three evaluation indicators: accuracy, recall, and harmonic mean, to observe the impact of the value of ε on the division of communities. The experimental results are shown in Figure 3. In each subgraph, as the value of ε increases, the original nodes in the community are deleted because they do not meet the conditions, which leads to an increase in the precision and a decrease in the recall. This satisfies the mutual restriction of precision and recall. The value of F‐score increases first and then gradually decreases. Since we convert the trust value between users into a distance value, when the trust value between users is greater, the distance is smaller, and the possibility of being in the same community is greater. When users have a small trust value, they have a large distance between them, and the possibility of being in the same community is relatively small. When the value of F‐score reaches the maximum, in each subgraph, the value of corresponding ε gradually increases from 0.3 to 0.4. At this time, the quality of community division is the best. It can be seen that the value of ε can be divided into two situations. When the social attribute has a high similarity with the community theme, ε=0.4. On the contrary, when the similarity between the social attribute and the community theme is weak, ε=0.3.Figure 3
Experimental results of differentε values in the synthetic network.


#### 5.2.2. Community Overlap Analysis

In this paper, based on the synthetic data set, we compare the proposed algorithm with the single-layer network community detection algorithm and the multilayer network community detection algorithm, respectively, to verify the community overlap performance of the proposed algorithm.We chose some classic single-layer network community detection algorithms, such as local optimization algorithm (LCDNN) [12], improved label propagation algorithm (TNS-LPA) [14], multiobjective optimization algorithm (PMOEA) [15], and nonnegative matrix factorization community detection algorithm (MOCBT) [16].We also choose some high-performance multilayer network community discovery algorithms, such as multilayer network community detection algorithm based on semisupervised nonnegative matrix factorization (S2-JNMF) [27], multiobjective optimization-based multilayer network overlap community detection algorithm (OMCS) [18], and the MTLCD [28] algorithm that expresses the trust relationship in the form of a tensor.In this paper, we adopt the idea of expansion and merging [17] and apply the single-layer network community detection algorithm to the multilayer network. It can be seen from Figure 4 that as the matching degree δ gradually increases, the ratio of the proposed algorithm to correctly identify nodes is significantly higher than that of the comparison algorithm. δ reflects the degree of similarity between the social attributes and the community theme set. The smaller the value of δ, the more chaotic the node partition. As the value of δ increases, node partitions become clearer, and the accuracy of overlapping nodes falling into different communities gradually improves. In general, the proposed algorithm has better performance in detecting overlapping communities.Figure 4
The proportion of each algorithm correctly identifying the classification node. (a) The experimental comparison between the algorithm proposed in this article and the single-layer network community discovery algorithm. (b) The experimental comparison between the algorithm proposed in this paper and the algorithm of multilayer network community discovery.
(a)(b)


#### 5.2.3. Verify Nature 2

We conduct experimental analysis on the synthetic network and the real network, respectively, to verify the correctness ofnature 2.By adjusting the matching degreeδ, we observe the changes in the community. The value of δ is 0.3-1, corresponding to 8 synthetic networks. The experimental results are shown in Figure 5. As the value of δ increases, the quality of community detection is better. When δ=1, the community detection basically tends to be stable, and the detection result is the best. The experimental results show that the structural relationship of user nodes is only a prerequisite for the formation of communities, and what really matters is the social attributes of user nodes.Figure 5
Schematic diagram of community detection of synthetic multilayer social network.We split the proposed algorithm according to social attribute features and structural features and divide it into a community detection algorithm that only considers social attribute features (PMOCBT), a community detection algorithm that only considers structural features (SMOCBT), and the proposed algorithm (MOCBT). The experimental results are shown in Figure6. In the four real data sets, the Q value of the SMOCBT algorithm is significantly lower than that of the PMOCBT and MOCBT algorithms. At the same time, the Q value of the PMOCBT algorithm is closer to that of MOCBT. The experimental results further show the correctness of the proposed nature 2.Figure 6
TheQ value of each algorithm in the real network.


#### 5.2.4. Compared with Other Algorithms on the Synthetic Network

The experimental results are shown in Table3. It can be seen from the table that the evaluation index of the proposed algorithm is significantly better than that of other single-layer network community detection algorithms. Multilayer networks cover a variety of complex relationships between users and are a further extension of single-layer networks. The proposed algorithm not only considers the user’s structural relationship but also combines the user’s attribute characteristics, so that the community detection result is significantly better than the single-layer network.Table 3
Experimental results of the proposed algorithm and each single-layer community detection algorithm in the synthetic network.
Data setEvaluation indexLCDNNTNS-LPAPMOEAMDNMFMOCBTG1Q0.5030.5160.5720.5810.624F‐score0.5290.5700.5930.5990.617G2Q0.5860.5940.6010.6110.688F‐score0.6140.6070.6260.6370.736G3Q0.6300.6240.6170.6490.690F‐score0.6340.6490.6400.6710.708G4Q0.6610.6380.6400.6610.704F‐score0.6910.6620.6990.6720.838G5Q0.6820.6490.6800.6940.715F‐score0.7160.6980.7240.7150.775G6Q0.7380.7040.7150.7280.826F‐score0.8010.7360.7470.7830.866G7Q0.7830.7800.7460.7720.904F‐score0.8240.8160.7930.8240.941G8Q0.8670.8420.8340.8820.954F‐score0.8900.9030.9060.8980.971It can be seen from Table4 that the evaluation index of the MTLCD algorithm based on the trust relationship is significantly better than that of the S2-JNMF and OMCS algorithms based on the structure relationship, and the proposed algorithm has the best performance compared to other comparison algorithms. The MTLCD algorithm obtains local communities on the network by establishing a trust model. The experimental results show that using the trust value to divide the community has better performance. However, this trust model essentially only uses the structural characteristics of the node, while ignoring the attribute characteristics of the node. Our proposed algorithm combines the characteristics of social attributes to ingeniously transform the complex relationships of multilayer social networks into trust relationships between users. We use the local information of the core node to divide the community and discard the inaccurate community results brought by the global information of the network, and the proposed algorithm shows a better detection result. In the data set G1, since the matching degree is low, the values of Q and F‐score are relatively low. In data set G8, since the matching degree is the largest, the values of Q and F‐score are relatively high. This fits our description of the nature of the community.Table 4
Experimental results of the proposed algorithm and each multilayer community detection algorithm in the synthetic network.
Data setEvaluation indexS2-JNMFOMCSMTLCDMOCBTG1Q0.5450.5750.6070.623F‐score0.6020.6090.6100.618G2Q0.6480.6370.6640.688F‐score0.6320.6460.7110.736G3Q0.6410.6360.6480.691F‐score0.6760.6880.6930.708G4Q0.6760.6640.6930.704F‐score0.7360.7710.8010.838G5Q0.7020.7000.7090.715F‐score0.7510.7430.7650.775G6Q0.8030.8010.8130.826F‐score0.8490.8310.8570.866G7Q0.8810.8490.8990.904F‐score0.9070.8970.9130.941G8Q0.9010.9310.9400.958F‐score0.9300.9240.9550.972


#### 5.2.5. Compared with Other Algorithms on the Real Network

We use four real multilayer social network data sets, namely, Twitter number, QQ Zone, Bio GRI, and Remote Sensing data sets, to verify the feasibility and scalability of our proposed algorithm. Since the result of a community in a given real network is unknown, this paper uses modularity as a measure of community detection. It can be seen from Table5 that the community results of the MTLCD algorithm based on the trust relationship are better than those of the S2-JNMF and OMCS algorithms based on the structural relationship. Compared with other comparison algorithms, our proposed algorithm has the best evaluation index. It can be seen that the trend of the real network experiment results is similar to that of the synthetic network. At the same time, in these two data sets, the modularity Q is greater than 0.5, which meets the standards of community testing [32].Table 5
Experimental results of each algorithm in the real network.
Comparison algorithmTwitterQQ ZoneBio GRIDRemote SensingPMOEA0.6350.6210.5480.579MDNMF0.6250.5990.5860.610TNS-LPA0.6650.6190.6010.622LCDNN0.6520.6250.5990.617S2-JNMF0.7290.6880.6450.680OMCS0.7350.6910.6230.667MTLCD0.7480.7100.6510.689MOCBT0.7530.7240.6860.703


## 5.1. Data Set and Evaluation Indicators

We use the random model [31] to generate 8 multilayer synthetic social networks with different structure types according to the matching degree δ of the community and social attributes. The matching degree of the 8 synthetic networks is increased from 0.3 to 1. The matching degree is described as the similarity between the social attribute and the community theme set. In other words, when δ=0.3, it indicates that the probability of the user’s social attribute appearing in the community theme set is 0.3. The greater the probability, the higher the similarity. Each network is composed of 4 layers, and each layer adopts a different generation model. Each network is divided into two overlapping communities, including 100 nodes and 8 social attributes. As shown in Table 1, V represents the number of nodes and E represents the number of edges. P represents the number of social attribute features, and C represents the number of communities. L represents the number of network layers.Table 1
Synthetic data set.
Data setVEPCLδG11004008240.3G21004008240.4G31004008240.5G41004008240.6G51004008240.7G61004008240.8G71004008240.9G81004008241As shown in Table2, we use four real multilayer social network data sets [28], such as Twitter data set, QQ Zone data set, Remote Sensing, and Bio GRID. The Twitter data set contains various topics such as entertainment, science, and sports and is divided into three levels: mention, repost, and reply. The QQ Zone data set collects the user’s spatial data information, including the user’s age and gender. The data set is divided into three levels: posting, comment, and like. The Remote Sensing data set is a network structure derived from satellite remote sensing images and contains five levels. Bio GRID contains human genetic data and various protein interaction data and consists of seven layers. The way the proteins interact in each layer is different.(1)
Extended modularity,Q: since we considered the structure and attribute relationships of nodes, in order to measure the quality of overlapping communities, inspired by the literature [32], we rewrite the modularity as(8)Q=12m∑i=1∣C∣∑p,q∈CiApq−fpfq2mdp,hidq,hi,where C represents the number of communities in the network, Apq represents the weight between the node p and q, m represents the sum of the weights of all edges in the network, and fpfq/2m represents the possibility that the nodes p and q are connected in a random state. If the node p completely belongs to the community where the core node hi is located; then dp,hi=1. If node p does not completely belong to the community where core node hi is located, the value range of dp,hi satisfies 0<dp,hi<1. Otherwise, dp,hi=0.(2)
Harmonic mean value,F‐score [33]: F‐score is a comprehensive measure of precision and recall. The closer F‐score is to 1, the closer the community divided by the algorithm is to the real community(9)F‐score=2×precision×recallprecision+recall.Table 2
Real data set.
Data setVELTwitter4385379918543QQ zone56206280552363Bio GRID38,936342,5997Remote Sensing64243415


## 5.2. Experimental Results and Analysis

In order to verify the effectiveness of our proposed algorithm, the following five experiments are designed:(1)
By changing the value of parameterε, we observe the changes in the evaluation index in the synthetic data set to determine the appropriate value of ε(2)
We selected 11 representative community discovery algorithms to compare with the proposed algorithm to verify the community overlap performance of the proposed algorithm(3)
Through the analysis of the community detection results of the synthetic network and the real network, we verify the correctness of the proposed community nature(4)
In the synthetic network, we compare and analyze the proposed algorithm with the contrast algorithm(5)
In the real network, we compare and analyze the proposed algorithm with the contrast algorithmThroughout the experiment, according to a previous literature, we set the parameterσ=1.866. β reflects the degree of community overlap. The higher the value of β, the more nodes shared between communities. In order to reduce community redundancy, we set a fusion threshold γ. That is, when β>γ, it indicates that communities with many nodes in common can be merged into one community. The higher the value of γ, the smaller the number of final communities. In this article, we set γ=0.75 [27].


### 5.2.1. The Value of Parameterε

In this section, we discuss the influence of parameterε on the proposed algorithm. In the 8 synthetic networks, we use three evaluation indicators: accuracy, recall, and harmonic mean, to observe the impact of the value of ε on the division of communities. The experimental results are shown in Figure 3. In each subgraph, as the value of ε increases, the original nodes in the community are deleted because they do not meet the conditions, which leads to an increase in the precision and a decrease in the recall. This satisfies the mutual restriction of precision and recall. The value of F‐score increases first and then gradually decreases. Since we convert the trust value between users into a distance value, when the trust value between users is greater, the distance is smaller, and the possibility of being in the same community is greater. When users have a small trust value, they have a large distance between them, and the possibility of being in the same community is relatively small. When the value of F‐score reaches the maximum, in each subgraph, the value of corresponding ε gradually increases from 0.3 to 0.4. At this time, the quality of community division is the best. It can be seen that the value of ε can be divided into two situations. When the social attribute has a high similarity with the community theme, ε=0.4. On the contrary, when the similarity between the social attribute and the community theme is weak, ε=0.3.Figure 3
Experimental results of differentε values in the synthetic network.


### 5.2.2. Community Overlap Analysis

In this paper, based on the synthetic data set, we compare the proposed algorithm with the single-layer network community detection algorithm and the multilayer network community detection algorithm, respectively, to verify the community overlap performance of the proposed algorithm.We chose some classic single-layer network community detection algorithms, such as local optimization algorithm (LCDNN) [12], improved label propagation algorithm (TNS-LPA) [14], multiobjective optimization algorithm (PMOEA) [15], and nonnegative matrix factorization community detection algorithm (MOCBT) [16].We also choose some high-performance multilayer network community discovery algorithms, such as multilayer network community detection algorithm based on semisupervised nonnegative matrix factorization (S2-JNMF) [27], multiobjective optimization-based multilayer network overlap community detection algorithm (OMCS) [18], and the MTLCD [28] algorithm that expresses the trust relationship in the form of a tensor.In this paper, we adopt the idea of expansion and merging [17] and apply the single-layer network community detection algorithm to the multilayer network. It can be seen from Figure 4 that as the matching degree δ gradually increases, the ratio of the proposed algorithm to correctly identify nodes is significantly higher than that of the comparison algorithm. δ reflects the degree of similarity between the social attributes and the community theme set. The smaller the value of δ, the more chaotic the node partition. As the value of δ increases, node partitions become clearer, and the accuracy of overlapping nodes falling into different communities gradually improves. In general, the proposed algorithm has better performance in detecting overlapping communities.Figure 4
The proportion of each algorithm correctly identifying the classification node. (a) The experimental comparison between the algorithm proposed in this article and the single-layer network community discovery algorithm. (b) The experimental comparison between the algorithm proposed in this paper and the algorithm of multilayer network community discovery.
(a)(b)


### 5.2.3. Verify Nature 2

We conduct experimental analysis on the synthetic network and the real network, respectively, to verify the correctness ofnature 2.By adjusting the matching degreeδ, we observe the changes in the community. The value of δ is 0.3-1, corresponding to 8 synthetic networks. The experimental results are shown in Figure 5. As the value of δ increases, the quality of community detection is better. When δ=1, the community detection basically tends to be stable, and the detection result is the best. The experimental results show that the structural relationship of user nodes is only a prerequisite for the formation of communities, and what really matters is the social attributes of user nodes.Figure 5
Schematic diagram of community detection of synthetic multilayer social network.We split the proposed algorithm according to social attribute features and structural features and divide it into a community detection algorithm that only considers social attribute features (PMOCBT), a community detection algorithm that only considers structural features (SMOCBT), and the proposed algorithm (MOCBT). The experimental results are shown in Figure6. In the four real data sets, the Q value of the SMOCBT algorithm is significantly lower than that of the PMOCBT and MOCBT algorithms. At the same time, the Q value of the PMOCBT algorithm is closer to that of MOCBT. The experimental results further show the correctness of the proposed nature 2.Figure 6
TheQ value of each algorithm in the real network.


### 5.2.4. Compared with Other Algorithms on the Synthetic Network

The experimental results are shown in Table3. It can be seen from the table that the evaluation index of the proposed algorithm is significantly better than that of other single-layer network community detection algorithms. Multilayer networks cover a variety of complex relationships between users and are a further extension of single-layer networks. The proposed algorithm not only considers the user’s structural relationship but also combines the user’s attribute characteristics, so that the community detection result is significantly better than the single-layer network.Table 3
Experimental results of the proposed algorithm and each single-layer community detection algorithm in the synthetic network.
Data setEvaluation indexLCDNNTNS-LPAPMOEAMDNMFMOCBTG1Q0.5030.5160.5720.5810.624F‐score0.5290.5700.5930.5990.617G2Q0.5860.5940.6010.6110.688F‐score0.6140.6070.6260.6370.736G3Q0.6300.6240.6170.6490.690F‐score0.6340.6490.6400.6710.708G4Q0.6610.6380.6400.6610.704F‐score0.6910.6620.6990.6720.838G5Q0.6820.6490.6800.6940.715F‐score0.7160.6980.7240.7150.775G6Q0.7380.7040.7150.7280.826F‐score0.8010.7360.7470.7830.866G7Q0.7830.7800.7460.7720.904F‐score0.8240.8160.7930.8240.941G8Q0.8670.8420.8340.8820.954F‐score0.8900.9030.9060.8980.971It can be seen from Table4 that the evaluation index of the MTLCD algorithm based on the trust relationship is significantly better than that of the S2-JNMF and OMCS algorithms based on the structure relationship, and the proposed algorithm has the best performance compared to other comparison algorithms. The MTLCD algorithm obtains local communities on the network by establishing a trust model. The experimental results show that using the trust value to divide the community has better performance. However, this trust model essentially only uses the structural characteristics of the node, while ignoring the attribute characteristics of the node. Our proposed algorithm combines the characteristics of social attributes to ingeniously transform the complex relationships of multilayer social networks into trust relationships between users. We use the local information of the core node to divide the community and discard the inaccurate community results brought by the global information of the network, and the proposed algorithm shows a better detection result. In the data set G1, since the matching degree is low, the values of Q and F‐score are relatively low. In data set G8, since the matching degree is the largest, the values of Q and F‐score are relatively high. This fits our description of the nature of the community.Table 4
Experimental results of the proposed algorithm and each multilayer community detection algorithm in the synthetic network.
Data setEvaluation indexS2-JNMFOMCSMTLCDMOCBTG1Q0.5450.5750.6070.623F‐score0.6020.6090.6100.618G2Q0.6480.6370.6640.688F‐score0.6320.6460.7110.736G3Q0.6410.6360.6480.691F‐score0.6760.6880.6930.708G4Q0.6760.6640.6930.704F‐score0.7360.7710.8010.838G5Q0.7020.7000.7090.715F‐score0.7510.7430.7650.775G6Q0.8030.8010.8130.826F‐score0.8490.8310.8570.866G7Q0.8810.8490.8990.904F‐score0.9070.8970.9130.941G8Q0.9010.9310.9400.958F‐score0.9300.9240.9550.972


### 5.2.5. Compared with Other Algorithms on the Real Network

We use four real multilayer social network data sets, namely, Twitter number, QQ Zone, Bio GRI, and Remote Sensing data sets, to verify the feasibility and scalability of our proposed algorithm. Since the result of a community in a given real network is unknown, this paper uses modularity as a measure of community detection. It can be seen from Table5 that the community results of the MTLCD algorithm based on the trust relationship are better than those of the S2-JNMF and OMCS algorithms based on the structural relationship. Compared with other comparison algorithms, our proposed algorithm has the best evaluation index. It can be seen that the trend of the real network experiment results is similar to that of the synthetic network. At the same time, in these two data sets, the modularity Q is greater than 0.5, which meets the standards of community testing [32].Table 5
Experimental results of each algorithm in the real network.
Comparison algorithmTwitterQQ ZoneBio GRIDRemote SensingPMOEA0.6350.6210.5480.579MDNMF0.6250.5990.5860.610TNS-LPA0.6650.6190.6010.622LCDNN0.6520.6250.5990.617S2-JNMF0.7290.6880.6450.680OMCS0.7350.6910.6230.667MTLCD0.7480.7100.6510.689MOCBT0.7530.7240.6860.703


## 5.2.1. The Value of Parameterε

In this section, we discuss the influence of parameterε on the proposed algorithm. In the 8 synthetic networks, we use three evaluation indicators: accuracy, recall, and harmonic mean, to observe the impact of the value of ε on the division of communities. The experimental results are shown in Figure 3. In each subgraph, as the value of ε increases, the original nodes in the community are deleted because they do not meet the conditions, which leads to an increase in the precision and a decrease in the recall. This satisfies the mutual restriction of precision and recall. The value of F‐score increases first and then gradually decreases. Since we convert the trust value between users into a distance value, when the trust value between users is greater, the distance is smaller, and the possibility of being in the same community is greater. When users have a small trust value, they have a large distance between them, and the possibility of being in the same community is relatively small. When the value of F‐score reaches the maximum, in each subgraph, the value of corresponding ε gradually increases from 0.3 to 0.4. At this time, the quality of community division is the best. It can be seen that the value of ε can be divided into two situations. When the social attribute has a high similarity with the community theme, ε=0.4. On the contrary, when the similarity between the social attribute and the community theme is weak, ε=0.3.Figure 3
Experimental results of differentε values in the synthetic network.


## 5.2.2. Community Overlap Analysis

In this paper, based on the synthetic data set, we compare the proposed algorithm with the single-layer network community detection algorithm and the multilayer network community detection algorithm, respectively, to verify the community overlap performance of the proposed algorithm.We chose some classic single-layer network community detection algorithms, such as local optimization algorithm (LCDNN) [12], improved label propagation algorithm (TNS-LPA) [14], multiobjective optimization algorithm (PMOEA) [15], and nonnegative matrix factorization community detection algorithm (MOCBT) [16].We also choose some high-performance multilayer network community discovery algorithms, such as multilayer network community detection algorithm based on semisupervised nonnegative matrix factorization (S2-JNMF) [27], multiobjective optimization-based multilayer network overlap community detection algorithm (OMCS) [18], and the MTLCD [28] algorithm that expresses the trust relationship in the form of a tensor.In this paper, we adopt the idea of expansion and merging [17] and apply the single-layer network community detection algorithm to the multilayer network. It can be seen from Figure 4 that as the matching degree δ gradually increases, the ratio of the proposed algorithm to correctly identify nodes is significantly higher than that of the comparison algorithm. δ reflects the degree of similarity between the social attributes and the community theme set. The smaller the value of δ, the more chaotic the node partition. As the value of δ increases, node partitions become clearer, and the accuracy of overlapping nodes falling into different communities gradually improves. In general, the proposed algorithm has better performance in detecting overlapping communities.Figure 4
The proportion of each algorithm correctly identifying the classification node. (a) The experimental comparison between the algorithm proposed in this article and the single-layer network community discovery algorithm. (b) The experimental comparison between the algorithm proposed in this paper and the algorithm of multilayer network community discovery.
(a)(b)


## 5.2.3. Verify Nature 2

We conduct experimental analysis on the synthetic network and the real network, respectively, to verify the correctness ofnature 2.By adjusting the matching degreeδ, we observe the changes in the community. The value of δ is 0.3-1, corresponding to 8 synthetic networks. The experimental results are shown in Figure 5. As the value of δ increases, the quality of community detection is better. When δ=1, the community detection basically tends to be stable, and the detection result is the best. The experimental results show that the structural relationship of user nodes is only a prerequisite for the formation of communities, and what really matters is the social attributes of user nodes.Figure 5
Schematic diagram of community detection of synthetic multilayer social network.We split the proposed algorithm according to social attribute features and structural features and divide it into a community detection algorithm that only considers social attribute features (PMOCBT), a community detection algorithm that only considers structural features (SMOCBT), and the proposed algorithm (MOCBT). The experimental results are shown in Figure6. In the four real data sets, the Q value of the SMOCBT algorithm is significantly lower than that of the PMOCBT and MOCBT algorithms. At the same time, the Q value of the PMOCBT algorithm is closer to that of MOCBT. The experimental results further show the correctness of the proposed nature 2.Figure 6
TheQ value of each algorithm in the real network.


## 5.2.4. Compared with Other Algorithms on the Synthetic Network

The experimental results are shown in Table3. It can be seen from the table that the evaluation index of the proposed algorithm is significantly better than that of other single-layer network community detection algorithms. Multilayer networks cover a variety of complex relationships between users and are a further extension of single-layer networks. The proposed algorithm not only considers the user’s structural relationship but also combines the user’s attribute characteristics, so that the community detection result is significantly better than the single-layer network.Table 3
Experimental results of the proposed algorithm and each single-layer community detection algorithm in the synthetic network.
Data setEvaluation indexLCDNNTNS-LPAPMOEAMDNMFMOCBTG1Q0.5030.5160.5720.5810.624F‐score0.5290.5700.5930.5990.617G2Q0.5860.5940.6010.6110.688F‐score0.6140.6070.6260.6370.736G3Q0.6300.6240.6170.6490.690F‐score0.6340.6490.6400.6710.708G4Q0.6610.6380.6400.6610.704F‐score0.6910.6620.6990.6720.838G5Q0.6820.6490.6800.6940.715F‐score0.7160.6980.7240.7150.775G6Q0.7380.7040.7150.7280.826F‐score0.8010.7360.7470.7830.866G7Q0.7830.7800.7460.7720.904F‐score0.8240.8160.7930.8240.941G8Q0.8670.8420.8340.8820.954F‐score0.8900.9030.9060.8980.971It can be seen from Table4 that the evaluation index of the MTLCD algorithm based on the trust relationship is significantly better than that of the S2-JNMF and OMCS algorithms based on the structure relationship, and the proposed algorithm has the best performance compared to other comparison algorithms. The MTLCD algorithm obtains local communities on the network by establishing a trust model. The experimental results show that using the trust value to divide the community has better performance. However, this trust model essentially only uses the structural characteristics of the node, while ignoring the attribute characteristics of the node. Our proposed algorithm combines the characteristics of social attributes to ingeniously transform the complex relationships of multilayer social networks into trust relationships between users. We use the local information of the core node to divide the community and discard the inaccurate community results brought by the global information of the network, and the proposed algorithm shows a better detection result. In the data set G1, since the matching degree is low, the values of Q and F‐score are relatively low. In data set G8, since the matching degree is the largest, the values of Q and F‐score are relatively high. This fits our description of the nature of the community.Table 4
Experimental results of the proposed algorithm and each multilayer community detection algorithm in the synthetic network.
Data setEvaluation indexS2-JNMFOMCSMTLCDMOCBTG1Q0.5450.5750.6070.623F‐score0.6020.6090.6100.618G2Q0.6480.6370.6640.688F‐score0.6320.6460.7110.736G3Q0.6410.6360.6480.691F‐score0.6760.6880.6930.708G4Q0.6760.6640.6930.704F‐score0.7360.7710.8010.838G5Q0.7020.7000.7090.715F‐score0.7510.7430.7650.775G6Q0.8030.8010.8130.826F‐score0.8490.8310.8570.866G7Q0.8810.8490.8990.904F‐score0.9070.8970.9130.941G8Q0.9010.9310.9400.958F‐score0.9300.9240.9550.972


## 5.2.5. Compared with Other Algorithms on the Real Network

We use four real multilayer social network data sets, namely, Twitter number, QQ Zone, Bio GRI, and Remote Sensing data sets, to verify the feasibility and scalability of our proposed algorithm. Since the result of a community in a given real network is unknown, this paper uses modularity as a measure of community detection. It can be seen from Table5 that the community results of the MTLCD algorithm based on the trust relationship are better than those of the S2-JNMF and OMCS algorithms based on the structural relationship. Compared with other comparison algorithms, our proposed algorithm has the best evaluation index. It can be seen that the trend of the real network experiment results is similar to that of the synthetic network. At the same time, in these two data sets, the modularity Q is greater than 0.5, which meets the standards of community testing [32].Table 5
Experimental results of each algorithm in the real network.
Comparison algorithmTwitterQQ ZoneBio GRIDRemote SensingPMOEA0.6350.6210.5480.579MDNMF0.6250.5990.5860.610TNS-LPA0.6650.6190.6010.622LCDNN0.6520.6250.5990.617S2-JNMF0.7290.6880.6450.680OMCS0.7350.6910.6230.667MTLCD0.7480.7100.6510.689MOCBT0.7530.7240.6860.703


## 6. Conclusion and Summary

Although traditional community detection algorithms based on trust relationships greatly improve the accuracy of community discovery, these methods rely excessively on the structural characteristics of the network. Therefore, to solve the problem of the lack of social attributes when constructing user trust relationships in multilayer social networks, we propose a multilayer social network overlapping community detection algorithm based on trust relationship. By integrating structural trust and social attribute trust, we transform a complex multilayer social network into a single-layer trust network. Based on the community discovery algorithm of trust value, we obtain the overlapping community structure of multilayer social networks. We carried out experimental comparative analysis on the synthetic network and the real network, respectively. The experimental results show that the proposed algorithm has higherQ and F‐score compared with other algorithms of the same type, which effectively reveals the community structure of the network. However, the user’s trust relationship is not static, but changes over time. Therefore, in a future work, we will focus on how to establish a dynamic trust model and design a fast and efficient dynamic overlapping community discovery algorithm.



---

*Source: 9268039-2021-11-10.xml*