# A Generalized Modularity for Computing Community Structure in Fully Signed Networks

Authors: Xiaochen He; Ruochen Zhang; Bin Zhu
Journal: Complexity
 (2023)

---

## Abstract

The community structure in fully signed networks that considers both node attributes and edge signs is important in computational social science; however, its physical description still requires further exploration, and the corresponding measurement remains lacking. In this paper, we present a generalized framework of community structure in fully signed networks, based on which a variant of modularity is designed. An optimization algorithm that maximizes modularity to detect potential communities is also proposed. Experiments show that the proposed method can efficiently optimize the objective function and perform effective community detection.


---

## Body

## 1. Introduction

Due to improved capacity of collecting network data, there has been substantial interest in studying network structures in computational social science [1, 2]. One focus of this field of research on network structure has concerned community structure [3]. Community structure is a known feature that is encountered in many applications of real-world systems [4]. Examples have been demonstrated in scientific collaboration networks [5], protein networks [6], citation networks [7], collegiate networks [8], sponge-microbiome networks [9], and brain functional networks [10]. Community in the field of social science usually refers to a cohesive group of members who share a common value and group identity, and have deep knowledge that links microlevel and macrolevel of sociological theories [11, 12] (e.g., social identity theory [13]). Emerging computational social science strongly relies on computationally intensive tools for modeling and analyzing social phenomena, while the analysis of community structure is a key method [1, 14].A community in a network is loosely defined and can be referred to as a class, a module, or a cluster [15]. The term community structure is generally derived from the mechanism of connection preference [15], which implies a natural division of nodes into several densely connected subgroups such that relationships within the subgroup are denser than the connections between subgroups [3, 16, 17]. To date, various measures, such as edge betweenness [3, 18], edge clustering coefficient [16], k-plexes [19], structural similarity [20], resistance distance [21], matrices’ eigenvectors [17], and node similarity [22], have been proposed to formulate the features of community structure. Although these measures are yet to be standardized, modularity is by far the most popular and has been shown to be efficient in measuring and detecting potential communities [18, 23, 24]. Modularity is proposed based on the difference between real and expected node connectivity [18]. Variants of this index have since been proposed to solve the resolution limit problem [25, 26]; to detect overlapping and hierarchical community structures [27, 28]; to manage directed, weighted networks, or multilayer networks [29–32]; to capture the evolution of communities [33]; and to consider node contributions [34].To detect potential communities, various types of algorithms have been proposed, such as label-propagation algorithms [35, 36], block-approximation algorithms [37], and modularity-maximizations [3, 17]. Among these methods, modularity-maximization-based algorithms are the most popular and formulate the problem of community detection into an optimization problem. Because the problem of modularity maximization is NP-hard, many heuristic algorithms have been introduced to detect communities in a reasonable time [12, 15, 24]. The most representative are greedy algorithms, which maximize modularity by aggregating communities [38, 39], and genetic algorithms, which iteratively increase modularity by crossover and mutation algorithms [40–42]. These methods have been shown to be efficient when solving the community detection problem, even with local optima [15, 24].Most relevant works were conducted on nonnegative networks, and researchers have paid a lot of attention to the subgraph density of nonnegative connections. However, the impact of negative relations has been ignored. In reality, interactions among individuals are not only friendly or cooperative relationships but may also be subject to contradictive or defective relationships [43, 44]. Firms competing on new standards of innovation may have both opposing and cooperative groups [45]. A collective action contains both the internal identity of the same community and the hostility between communities [46]. Networks that consist of both positive and negative edges are called signed networks [43]. To our knowledge, only a few studies have focused on the community structure in signed networks. Gómez et al. [47] proposed a generalized idea of community structure in signed networks, according to which the positive relationships within the same community are denser than the positive relationships between different communities, and the negative relationships between communities are denser than the negative relationships within the same community. They also proposed a modified modularity that measures the new feature of community structure in signed networks.Equaling the importance of edges in network analysis, node attributes also play a fundamental role in individual aggregation [48, 49]. Du et al. [50] introduced the notion of the node attribute into the signed network and referred to a network that contained both node and edge signs as a fully signed network. He et al. [51] analyzed the balance status of the Chinese rural system using data on migrant workers’ civil rights awareness (node attribute) and their information-diffusion networks (edge attribute). Studies of fully signed networks considering both node and edge attributes enrich traditional empirical research methods and broaden the application of network science in social science. However, the question of how to use community structure analysis in a fully signed network has still not been explored.Although a few existing studies have focused on the node attributes in community detection, most investigated attributes were just related to the structural attributes or the specific position in the network. For example, Saoud and Moussaoui [22] used the similarity between each pair of nodes’ attributes of the structural feature to find the potential communities. Dabaghi Zarandi and Kuchaki Rafsanjani [20] focused on the number of common neighbors of each pair of nodes, and by use, they identified the intercommunity and intracommunity edges. However, these studies neglected personal node attributes that are independent from network attributes; thus, existing research fails to combine macrocosmic network community analysis with microcosmic individual analysis. This study aims to fill this gap. The analysis of node attributes is necessary because they have a strong impact on the formation of communities [48, 49]. Therefore, the combination of edge and node attributes helps detect more natural communities. When studying fully signed networks, Du et al. noted that people with similar node attributes gather into a group of friends based on homophily theory [50]. In what follows, we present a generalized framework of community structure in fully signed networks based on the rule of homophily, as shown in Figure 1. In studies of community detection in general networks, researchers primarily focus on the density of subgraphs or the similarity between each pair of nodes’ structural attributes. The importance of individual attributes and the relationship between nodes and edges are emphasized when we detect communities in fully signed networks. When we introduce the individual attribute, nodes with the same personal attributes are possibly classified into the same community, regardless of the subgraph density. Additionally, the different effects of the positive and negative relationships are considered when the edge sign is introduced, and the final identified communities are different from the results acquired by the existing studies.Figure 1
Illustration that explains the difference between the present study and existing studies.The remainder of this paper is organized as follows. Section2 discusses the feature of community balance in fully signed networks and proposes a new measurement. Section 3 presents an optimal algorithm to detect a generalized community structure. Section 4 presents experiments with the proposed method on computer-generated and real-world networks. Section 5 presents the conclusion and recommendations for future work.


## 2. Community Structure in Fully Signed Networks and Its Measurement

### 2.1. Community Structure and Modularity

A community refers to a cohesive subset of nodes in a heterogeneous network, while the community structure (Figure2) is a special structure in which the relationships between nodes within the same community are denser than the relationships between different communities [18].Figure 2
Illustration of a community structure.By measuring the difference between the probability of having edges falling within communities and the expected probability in an equivalent random network with the same number of edges and nodes, Newman and Girvan [18] proposed the modularity formulated as given in the following equation:(1)Q=12ω∑i∑jωij−ωiωj2ωδCi,Cj,where Ci is the community to which node i belongs; δCi,Cj=1 when i and j belong to the same community, and δCi,Cj=0 otherwise; ωij=1 when i and j are connected, and ωij=0 when i and j are disconnected; ωi=∑jωij is the degree of node i; and 2ω=∑iωi=∑i∑jωij is the total degree in the network. Then, ωi/2ω is the probability of node i connecting with other nodes in the null case, ωi/2ω⋅ωj/2ω is the probability of nodes i and j being connected, and ωiωj/2ω represents the corresponding expected value. A larger Q indicates a closer internal connection of the community and a more marked feature of the community structure.


### 2.2. Signed Networks, Structural Balance, and Community Structure

Structural balance theory plays an important role in predicting the aggregation process of individuals in signed networks [52]. Heider first proposed the concept of structural balance and explained the root of conflicts based on tripartite relations [53]. Figure 3 shows different types of triangles, where Figures 3(a) and 3(b) are balanced triangles, while Figures 3(c) and 3(d) are imbalanced triangles, according to [53], and all triangles in a balanced network are balanced triangles. Davis [54] then generalized the definition into the weak form of balance and pointed out that Figure 3(d) is also the balanced triangle. From a global view, a balanced network can be divided into several clusters, within which all the edges are positive and between which all the edges are negative [51].Figure 3
All types of triangles in signed networks. The solid lines denote positive edges, and the dashed lines denote negative edges. According to Davis’s theory, (a), (b), and (d) are balanced triangles, while triangle (c) is imbalanced.
(a)(b)(c)(d)According to balance theory, Gómez et al. [47] generalized the modularity in signed networks, according to which the positive edges increase the mutual recognition between individuals and thus promote the formation of the community, while the conflict derived from the negative relationship are the shackles of the formation of the community. Therefore, positive edges should be assigned within the community, and negative edges should be assigned between communities as much as possible. The generalized modularity is formulated as given in the following equation:(2)QE=2ω+2ω++2ω−QE++2ω−2ω++2ω−QE−,QE+=12ω+∑i∑ji≠jωij+−ωi+ωj+2ω+δCi,Cj,QE−=12ω−∑i∑ji≠jωij−−ωi−ωj−2ω−1−δCi,Cj,where QE+ (QE−) is the comparison between the probability of having positive (negative) edges falling within (between) communities and the expected probability in a random network with the same positive-edge (negative-edge) degree; ωij+ (ωij−) is the existence of a positive (negative) edge between nodes i and j, where ωij+=1 (ωij−=1) if they are positively (negatively) connected, and otherwise ωij+=0 (ωij−=0); and ωi+=∑jωij+ is the positive-edge degree of node i, and ωi−=∑jωij− denotes its negative-edge degree. Then, 2ω+=∑iωi+=∑i∑jωij+ is the total degree of positive edges, and 2ω−=∑iωi−=∑i∑jωij− is the total degree of negative edges. ωi+/2ω+ (ωi−/2ω−) is the probability of node i being positively (negatively) connected with other nodes, and ωi+ωj+/2ω+ (ωi−ωj−/2ω−) is the expected value of node i being positively (negatively) connected with node j. When all edges are positive, equation (2) can be transformed to equation (1).


### 2.3. Community Structure in Fully Signed Networks

Networks consisting of both node and edge signs are called fully signed networks [50]. The edge signs “+” or “−” represent the positive or negative edges, while node signs “+” or “−” may indicate a demographical attribute, such as the party. The fully signed network can be formulated as G=V,E, where vi∈V⟶+1,−1 is the node sets and eij∈E⟶+1,−1 is the node edges. However, the node attribute is only binary if the sign is assigned to “+” or “−.” In this study, we generalize the node attribute into a multicategory attribute, and the node attribute can be assigned to 1, 2, 3, …, i.e., vi∈V⟶1,2,3.... This setting can describe a more closed real-world case; for example, the multicategory attribute can represent an individual’s nationality, party, religious beliefs, or shape of face.According to Du et al. [50], a fully signed network is balanced if nodes with the same attribute are positively connected, while nodes with different attributes are negatively connected; thus, only three triangles are balanced, as shown in Figure 4.Figure 4
All balanced triangles in fully signed networks. The solid lines denote positive edges, and the dashed lines denote negative edges. The different shapes of nodes represent the node attributes.
(a)(b)(c)Combined with the idea of community structure proposed by Gómez et al. [47] and the balance theory, an ideal fully signed network with the feature of community structure can be divided into several communities, within which nodes with the same attribute are positively connected, while nodes with different attributes are negatively connected. Figure 5 shows an illustration of the ideal structure and can somehow explain some classic sociological theories. Taking social identity theory as an example, positive relationships and the same demographic attribute enhance community members’ sense of identity in their collective action, while hostile relationships and different demographic attributes promote intercommunity comparisons, leading to relative deprivation [55, 56].Figure 5
An ideal community structure in fully signed networks. The solid lines denote positive edges, and the dashed lines denote negative edges. The different shapes of nodes denote the node attributes. The dotted lines denote the communities.However, the ideal structure is too strict. If nodes 1 and 2 in Figure4 share different demographical attributes, they still contribute to the community structure according to the theory of Gómez et al. [47]. If two nodes with the same attribute are negatively connected, they can also be assigned to the same community due to homophily [48, 50, 51]. In this case, a dilemma between node attributes and edge signs exists. Only putting positive edges into the same community may violate the homophily principle, while assigning communities equal to node attributes may contradict the mechanism of structural balance. An effective measurement should separately consider the calculation of edge and node features instead of putting them together.Therefore, the community structure in fully signed networks should be divided into edge-community and node-community. The contribution of the edge-community feature is a positive edge assigned within the community or a negative edge located between communities, and the contribution of the node-community feature is a node that shares the same attribute with other nodes within a community or possessing a different attribute with others between different communities. We now present a new modularity function formulated as given in the following equation:(3)QF=λQN+1−λQE,QN=2b+2b++2b−⋅QN++2b−2b++2b−⋅QN−,QN+=12b+∑i∑ji≠jbij+−bi+⋅bj+2b+δCi,Cj,QN−=12b−∑i∑ji≠jbij−−bi−⋅bj−2b−1−δCi,Cj,where QN is the modularity for the node-community;QE is the modularity for the edge-community formulated as equation (2); λ is the weight of the node-community, and 1−λ represents the weight of the edge-community; and QN+ (QN−) is the comparison between the probability of two nodes sharing the same (different) attributes within (between) communities and the expected probability of two nodes having the same (different) attributes in the null case. To introduce the node attributes, it is necessary to construct a similarity matrix B. The element bij+ (bij−) in B represents the similarity (dissimilarity) between nodes i and j, bij+=1 (bij−=1) if they share the same (different) attributes, and bij+=0 (bij−=0) if they possess the different (same) attributes. bi+=∑jbij+ (bi−=∑jbij−) is the number of nodes that possess the same (different) attributes as node i. 2b+=∑ibi+=∑i∑jbij+ (2b−=∑ibi−=∑i∑jbij−) is the total degree of the matrix of similarity (dissimilarity). bi+/2b+ (bi−/2b−) is the probability of node i having the same (different) attribute as others, and bi+bj+/2b+ (bi−bj−/2b−) is the corresponding expected value of node i and node j possessing the same (different) attributes. When the weight of the node-community λ equals 0, equation (3) can be transformed to equation (2).We now present a normalized form of modularity that can weaken the endogeneity and resolution limit. Equation (1) can be transformed as equation (4), where epq is the fraction of degrees that connect nodes in community p to those in community q and nc is the number of communities. epp = epq when p equals q:(4)Q=∑p=1ncepp−∑q=1ncepq2.The classic modularityQ can reach its maximum when epq = 0 (p ≠ q), under which Q=∑p=1ncepp−∑p=1ncepp2=1−∑p=1ncepp2. Thus, maxQ=1−1/nc if e11=e22=⋯=encnc. Therefore, a nominalized Q can be formulized as given in the following equation [57]:(5)Q^=QmaxQ=ncnc−1⋅Q.In signed networks, the modularity for computing the positive-link effectQE+ in equation (2) can reach its maximum if epq+=0 and e11+=e22+=⋯=encnc+, and maxQE+=1−1/nc. Considering the effect of negative edges, QE− can be rewritten as QE−=∑p=1nc∑q=1p≠qncepq−−∑q=1ncepq−∑p=1ncepq−. When epp−=0, QE− can be maximized and QE−=1−∑q=1nc∑q=1p≠qnc∑q=1p≠qncepq−2. Then, we can acquire maxQE−=1−1/ncnc−1 when e12−=e13−=⋯=enc−1nc−. Based on equation (2), we can acquire the maximum of QE shown in equation (6), and thus, the nominalized QE can be formulized as equation (7):(6)maxQE=2ω+2ω++2ω−⋅maxQE++2ω−2ω++2ω−⋅maxQE−=ω++ω−ncnc−1−nc−1ω+−ω−ω++ω−ncnc−1,(7)Q^E=QEmaxQE=ω++ω−ncnc−1ω++ω−ncnc−1−nc−1ω+−ω−⋅QE.Similarly, we can also acquire the nominalized form ofQN for the node-community modularity Q^N=b++b−ncnc−1/b++b−ncnc−1−nc−1b+−b−⋅QN based on equation (3). Therefore, the adjusted modularity in fully signed networks that consider both node and edge attributes can be formulized as given in the following equation:(8)Q^F=λQ^N+1−λQ^E=b++b−ncnc−1λQNb++b−ncnc−1−nc−1b+−b−+ω++ω−ncnc−11−λQEω++ω−ncnc−1−nc−1ω+−ω−.Now, we present an illustration to compare the different types of modularity on different network structures. As shown in Figure6(a) is an ideal network with the feature of community structure, where nodes within the community have the same attribute and are closely connected by positive edges, while those between communities have different attributes and are negatively connected. Based on the ideal structure, Figure 6(b) transferred one edge within the community to the location between the communities to reduce the tightness of the relations within the community as well as the sparsity of the relations between communities. Figure 6(c) transformed a positive edge within the community to a negative edge, thus reducing the balance of the structure from the relationship level. Figure 6(d) adjusted an individual’s attribute so that node attributes within the community are no longer unified. Table 1 shows the calculation results of three types of modularity and their normalized values on these different network structures. Through comparison with the ideal structure, the classic modularity proposed by Newman and Girvan [18] can detect the general subtle change in the density within and between communities but fails to find the changes in edge signs and node attributes. The modularity proposed by Gómez et al. [47] can successfully detect the change in situations illustrated in Figures 6(b) and 6(c), but still cannot detect the change in nodes because it does not include the node-community feature in its expression. The proposed modularity can fully detect the changes in network structure, edge signs, and node attributes.Figure 6
Four similar network structures with subtle changes. (a) Is the ideal structure with the feature of community structure; (b) changes the community density; (c) changes one edge’s sign; (d) changes one node’s attribute. The solid lines denote positive edges, and the dashed lines denote negative edges. The different shapes of nodes denote the node attributes.
(a)(b)(c)(d)Table 1
Calculation results of three types of modularity for different networks in Figure6.
IndexSituation (a)Situation (b)Situation (c)Situation (d)GeneralQ0.64330.61390.64330.6433GeneralQ^0.85770.81850.85770.8577Classic signed networkQE0.69700.66720.65940.6970Classic signed networkQ^E0.91090.87190.85610.9109Fully signed networkQF (λ = 0.5)0.52940.51450.51060.5084Fully signed networkQ^F (λ = 0.5)0.66370.64420.63630.6398


## 2.1. Community Structure and Modularity

A community refers to a cohesive subset of nodes in a heterogeneous network, while the community structure (Figure2) is a special structure in which the relationships between nodes within the same community are denser than the relationships between different communities [18].Figure 2
Illustration of a community structure.By measuring the difference between the probability of having edges falling within communities and the expected probability in an equivalent random network with the same number of edges and nodes, Newman and Girvan [18] proposed the modularity formulated as given in the following equation:(1)Q=12ω∑i∑jωij−ωiωj2ωδCi,Cj,where Ci is the community to which node i belongs; δCi,Cj=1 when i and j belong to the same community, and δCi,Cj=0 otherwise; ωij=1 when i and j are connected, and ωij=0 when i and j are disconnected; ωi=∑jωij is the degree of node i; and 2ω=∑iωi=∑i∑jωij is the total degree in the network. Then, ωi/2ω is the probability of node i connecting with other nodes in the null case, ωi/2ω⋅ωj/2ω is the probability of nodes i and j being connected, and ωiωj/2ω represents the corresponding expected value. A larger Q indicates a closer internal connection of the community and a more marked feature of the community structure.


## 2.2. Signed Networks, Structural Balance, and Community Structure

Structural balance theory plays an important role in predicting the aggregation process of individuals in signed networks [52]. Heider first proposed the concept of structural balance and explained the root of conflicts based on tripartite relations [53]. Figure 3 shows different types of triangles, where Figures 3(a) and 3(b) are balanced triangles, while Figures 3(c) and 3(d) are imbalanced triangles, according to [53], and all triangles in a balanced network are balanced triangles. Davis [54] then generalized the definition into the weak form of balance and pointed out that Figure 3(d) is also the balanced triangle. From a global view, a balanced network can be divided into several clusters, within which all the edges are positive and between which all the edges are negative [51].Figure 3
All types of triangles in signed networks. The solid lines denote positive edges, and the dashed lines denote negative edges. According to Davis’s theory, (a), (b), and (d) are balanced triangles, while triangle (c) is imbalanced.
(a)(b)(c)(d)According to balance theory, Gómez et al. [47] generalized the modularity in signed networks, according to which the positive edges increase the mutual recognition between individuals and thus promote the formation of the community, while the conflict derived from the negative relationship are the shackles of the formation of the community. Therefore, positive edges should be assigned within the community, and negative edges should be assigned between communities as much as possible. The generalized modularity is formulated as given in the following equation:(2)QE=2ω+2ω++2ω−QE++2ω−2ω++2ω−QE−,QE+=12ω+∑i∑ji≠jωij+−ωi+ωj+2ω+δCi,Cj,QE−=12ω−∑i∑ji≠jωij−−ωi−ωj−2ω−1−δCi,Cj,where QE+ (QE−) is the comparison between the probability of having positive (negative) edges falling within (between) communities and the expected probability in a random network with the same positive-edge (negative-edge) degree; ωij+ (ωij−) is the existence of a positive (negative) edge between nodes i and j, where ωij+=1 (ωij−=1) if they are positively (negatively) connected, and otherwise ωij+=0 (ωij−=0); and ωi+=∑jωij+ is the positive-edge degree of node i, and ωi−=∑jωij− denotes its negative-edge degree. Then, 2ω+=∑iωi+=∑i∑jωij+ is the total degree of positive edges, and 2ω−=∑iωi−=∑i∑jωij− is the total degree of negative edges. ωi+/2ω+ (ωi−/2ω−) is the probability of node i being positively (negatively) connected with other nodes, and ωi+ωj+/2ω+ (ωi−ωj−/2ω−) is the expected value of node i being positively (negatively) connected with node j. When all edges are positive, equation (2) can be transformed to equation (1).


## 2.3. Community Structure in Fully Signed Networks

Networks consisting of both node and edge signs are called fully signed networks [50]. The edge signs “+” or “−” represent the positive or negative edges, while node signs “+” or “−” may indicate a demographical attribute, such as the party. The fully signed network can be formulated as G=V,E, where vi∈V⟶+1,−1 is the node sets and eij∈E⟶+1,−1 is the node edges. However, the node attribute is only binary if the sign is assigned to “+” or “−.” In this study, we generalize the node attribute into a multicategory attribute, and the node attribute can be assigned to 1, 2, 3, …, i.e., vi∈V⟶1,2,3.... This setting can describe a more closed real-world case; for example, the multicategory attribute can represent an individual’s nationality, party, religious beliefs, or shape of face.According to Du et al. [50], a fully signed network is balanced if nodes with the same attribute are positively connected, while nodes with different attributes are negatively connected; thus, only three triangles are balanced, as shown in Figure 4.Figure 4
All balanced triangles in fully signed networks. The solid lines denote positive edges, and the dashed lines denote negative edges. The different shapes of nodes represent the node attributes.
(a)(b)(c)Combined with the idea of community structure proposed by Gómez et al. [47] and the balance theory, an ideal fully signed network with the feature of community structure can be divided into several communities, within which nodes with the same attribute are positively connected, while nodes with different attributes are negatively connected. Figure 5 shows an illustration of the ideal structure and can somehow explain some classic sociological theories. Taking social identity theory as an example, positive relationships and the same demographic attribute enhance community members’ sense of identity in their collective action, while hostile relationships and different demographic attributes promote intercommunity comparisons, leading to relative deprivation [55, 56].Figure 5
An ideal community structure in fully signed networks. The solid lines denote positive edges, and the dashed lines denote negative edges. The different shapes of nodes denote the node attributes. The dotted lines denote the communities.However, the ideal structure is too strict. If nodes 1 and 2 in Figure4 share different demographical attributes, they still contribute to the community structure according to the theory of Gómez et al. [47]. If two nodes with the same attribute are negatively connected, they can also be assigned to the same community due to homophily [48, 50, 51]. In this case, a dilemma between node attributes and edge signs exists. Only putting positive edges into the same community may violate the homophily principle, while assigning communities equal to node attributes may contradict the mechanism of structural balance. An effective measurement should separately consider the calculation of edge and node features instead of putting them together.Therefore, the community structure in fully signed networks should be divided into edge-community and node-community. The contribution of the edge-community feature is a positive edge assigned within the community or a negative edge located between communities, and the contribution of the node-community feature is a node that shares the same attribute with other nodes within a community or possessing a different attribute with others between different communities. We now present a new modularity function formulated as given in the following equation:(3)QF=λQN+1−λQE,QN=2b+2b++2b−⋅QN++2b−2b++2b−⋅QN−,QN+=12b+∑i∑ji≠jbij+−bi+⋅bj+2b+δCi,Cj,QN−=12b−∑i∑ji≠jbij−−bi−⋅bj−2b−1−δCi,Cj,where QN is the modularity for the node-community;QE is the modularity for the edge-community formulated as equation (2); λ is the weight of the node-community, and 1−λ represents the weight of the edge-community; and QN+ (QN−) is the comparison between the probability of two nodes sharing the same (different) attributes within (between) communities and the expected probability of two nodes having the same (different) attributes in the null case. To introduce the node attributes, it is necessary to construct a similarity matrix B. The element bij+ (bij−) in B represents the similarity (dissimilarity) between nodes i and j, bij+=1 (bij−=1) if they share the same (different) attributes, and bij+=0 (bij−=0) if they possess the different (same) attributes. bi+=∑jbij+ (bi−=∑jbij−) is the number of nodes that possess the same (different) attributes as node i. 2b+=∑ibi+=∑i∑jbij+ (2b−=∑ibi−=∑i∑jbij−) is the total degree of the matrix of similarity (dissimilarity). bi+/2b+ (bi−/2b−) is the probability of node i having the same (different) attribute as others, and bi+bj+/2b+ (bi−bj−/2b−) is the corresponding expected value of node i and node j possessing the same (different) attributes. When the weight of the node-community λ equals 0, equation (3) can be transformed to equation (2).We now present a normalized form of modularity that can weaken the endogeneity and resolution limit. Equation (1) can be transformed as equation (4), where epq is the fraction of degrees that connect nodes in community p to those in community q and nc is the number of communities. epp = epq when p equals q:(4)Q=∑p=1ncepp−∑q=1ncepq2.The classic modularityQ can reach its maximum when epq = 0 (p ≠ q), under which Q=∑p=1ncepp−∑p=1ncepp2=1−∑p=1ncepp2. Thus, maxQ=1−1/nc if e11=e22=⋯=encnc. Therefore, a nominalized Q can be formulized as given in the following equation [57]:(5)Q^=QmaxQ=ncnc−1⋅Q.In signed networks, the modularity for computing the positive-link effectQE+ in equation (2) can reach its maximum if epq+=0 and e11+=e22+=⋯=encnc+, and maxQE+=1−1/nc. Considering the effect of negative edges, QE− can be rewritten as QE−=∑p=1nc∑q=1p≠qncepq−−∑q=1ncepq−∑p=1ncepq−. When epp−=0, QE− can be maximized and QE−=1−∑q=1nc∑q=1p≠qnc∑q=1p≠qncepq−2. Then, we can acquire maxQE−=1−1/ncnc−1 when e12−=e13−=⋯=enc−1nc−. Based on equation (2), we can acquire the maximum of QE shown in equation (6), and thus, the nominalized QE can be formulized as equation (7):(6)maxQE=2ω+2ω++2ω−⋅maxQE++2ω−2ω++2ω−⋅maxQE−=ω++ω−ncnc−1−nc−1ω+−ω−ω++ω−ncnc−1,(7)Q^E=QEmaxQE=ω++ω−ncnc−1ω++ω−ncnc−1−nc−1ω+−ω−⋅QE.Similarly, we can also acquire the nominalized form ofQN for the node-community modularity Q^N=b++b−ncnc−1/b++b−ncnc−1−nc−1b+−b−⋅QN based on equation (3). Therefore, the adjusted modularity in fully signed networks that consider both node and edge attributes can be formulized as given in the following equation:(8)Q^F=λQ^N+1−λQ^E=b++b−ncnc−1λQNb++b−ncnc−1−nc−1b+−b−+ω++ω−ncnc−11−λQEω++ω−ncnc−1−nc−1ω+−ω−.Now, we present an illustration to compare the different types of modularity on different network structures. As shown in Figure6(a) is an ideal network with the feature of community structure, where nodes within the community have the same attribute and are closely connected by positive edges, while those between communities have different attributes and are negatively connected. Based on the ideal structure, Figure 6(b) transferred one edge within the community to the location between the communities to reduce the tightness of the relations within the community as well as the sparsity of the relations between communities. Figure 6(c) transformed a positive edge within the community to a negative edge, thus reducing the balance of the structure from the relationship level. Figure 6(d) adjusted an individual’s attribute so that node attributes within the community are no longer unified. Table 1 shows the calculation results of three types of modularity and their normalized values on these different network structures. Through comparison with the ideal structure, the classic modularity proposed by Newman and Girvan [18] can detect the general subtle change in the density within and between communities but fails to find the changes in edge signs and node attributes. The modularity proposed by Gómez et al. [47] can successfully detect the change in situations illustrated in Figures 6(b) and 6(c), but still cannot detect the change in nodes because it does not include the node-community feature in its expression. The proposed modularity can fully detect the changes in network structure, edge signs, and node attributes.Figure 6
Four similar network structures with subtle changes. (a) Is the ideal structure with the feature of community structure; (b) changes the community density; (c) changes one edge’s sign; (d) changes one node’s attribute. The solid lines denote positive edges, and the dashed lines denote negative edges. The different shapes of nodes denote the node attributes.
(a)(b)(c)(d)Table 1
Calculation results of three types of modularity for different networks in Figure6.
IndexSituation (a)Situation (b)Situation (c)Situation (d)GeneralQ0.64330.61390.64330.6433GeneralQ^0.85770.81850.85770.8577Classic signed networkQE0.69700.66720.65940.6970Classic signed networkQ^E0.91090.87190.85610.9109Fully signed networkQF (λ = 0.5)0.52940.51450.51060.5084Fully signed networkQ^F (λ = 0.5)0.66370.64420.63630.6398


## 3. Algorithms to Detect Community Structure

To detect rational communities in fully signed networks, we present a modularity-maximization-based algorithm calledmaxQF. Because maximizing modularity is an NP-hard problem, it is difficult to solve using traditional algorithms [15]. In this section, we propose a memetic algorithm for community detection in fully signed networks (MA-CD) that combines the strength of a genetic algorithm (GA) and the local search function. The memetic algorithm has been shown to be effective when solving NP-hard problems [51, 58].


### 3.1. Encoding and Decoding

The solution of community detection is encoded as a chromosome consisting of a list of genes:Chromosome=g1,g2,g3,…,gN, where the gene gi denotes the community node i belongs to. An illustration of the encoding is shown in Figure 7. Given a network consisting of 15 nodes, the initial chromosome {1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3} indicates that nodes 1–5 are assigned to the first community, nodes 6–10 are assigned to the second community, and nodes 11–15 are assigned to the third community. The 10th gene is changed from 2 to 1, and the 12th gene is changed from 3 to 2. Then, node 10 is dragged to community 1 from community 2, and node 12 is dragged to community 2 from community 3. When the procedure of the algorithm stops, we reversely decode the acquired chromosome as the solution of community detection.Figure 7
An illustration of the encoding. The upper part denotes two chromosomes consisting of genes, and the lower part denotes the solution of community detection corresponding to the two chromosomes. The solid lines denote positive edges, and the dashed lines denote negative edges. The different shapes of nodes denote the node attributes. The numbers next to nodes represent the node sequence number, and the dotted lines represent the community assignments.


### 3.2. Algorithm Framework

Algorithm1 shows the framework of MA-CD. We need to input the matrix of the signed network, the attribute for each node, and the necessary parameters. We first use the function “Initialization” to initialize a population P that consists of Ps chromosomes. These chromosomes can be decoded to the solutions of the community detection problem. Then, the procedure enters into a loop, where we use the function “tournament” to choose chromosomes with higher modularity as the parental population Parent. This operation involves running several “tournaments” among a few individuals chosen at random from the population. Individuals with better fitness have a higher probability of being chosen [59]. The number of selected parental chromosomes equals the size of the mating pool (MPs). The mating pool is formed by parental chromosomes that the selection operators deem to have higher fitness. Individuals can be repeatedly included in the mating pool so that individuals of higher fitness are more likely to be chosen multiple times [60]. In the next step, the population Parent is proceeded by the function “Genetic,” which includes both crossover and mutation operations, and then generates an offspring population offspring. Next, the function “Local” is used with offspring to find the local optimized chromosome opt. We then use the function “Update” to keep chromosomes with fitter solutions among P, Parent, offspring, and opt. The procedure may break the loop when the iteration reaches 1000 or the modularity of the best solution remains unchangeable over 50 iterations. Finally, we output the best solution of the community structure and its corresponding modularity.Algorithm 1: Framework of MA-CD.
(1)
Parameters: size of population (Ps), size of tournament (Ts), size of mating pool (MPs), maximum number of communities (Cnum), number of nodes (N), weight of node-community (λ), and probability of crossover (Cp);(2)
Input: the network matrix (A), the node attributes (V);(3)
P⟵ Initialization (A, V, Ps, Cnum, N, and λ);(4)
Repeat(5)
Parent⟵ Tournament (P, Ts, and MPs);(6)
Offspring⟵ Genetic (Parent, Cp, N, and λ);(7)
Opt⟵ Local (Offspring, N, and Cnum, λ);(8)
P⟵ Update (P, Parent, Offspring, and Opt);(9)
Until Termination(10)
Decode (P);(11)
Output: the fittest community assignation and its corresponding modularity.


### 3.3. Initialization

Before we introduce the initialization procedure, we present two definitions for different types of neighbors: (1) given a focal nodei, the edge neighbors of i are those nodes that positively connect with i; and (2) its node neighbors are those that share the same attribute with i.In the initialization, we generate a population withPs chromosomes. For each chromosome, we assign a random number “1, 2, 3, …, Cnum” to each gene as the community to which the node belongs. We then introduce a priori knowledge to speed up the convergence of the procedure and generate a random number a from 0 to 1 for each node i: if a is smaller than or equal to the weight of node-community λ, we randomly choose one of i’s node-neighbors k and assign k’s community number to i’s i.e.,gi=gk; otherwise, we randomly choose one of i’s edge neighbors l and make i’s community the same as l’s i.e.,gi=gl. An illustration of the prior knowledge is shown in Figure 8.Figure 8
An illustration of the initialization. Given the focal node 5, if the random numbera ≤ λ, we randomly choose its node-neighbor (node 4) and assign node 5 to community 2 (the community to which node 4 belongs); if a > λ, we assign community 1 to node 5 because its edge-neighbor node 2 belongs to community 1.


### 3.4. Genetic Operation

Genetic operation is the primary step of the genetic algorithm and includes both crossover and mutation operations. In this step, we perform a two-point crossover procedure and a one-point mutation procedure. According to the global framework (Algorithm1), the crossover procedure is conducted with the probability Cp, while the mutation procedure is conducted with the probability 1 − Cp.During crossover, given two parental chromosomesC1 and C2, we randomly choose two points j and k (j < k). If a randomly generated number b ≤ 1/3, then all the genes from the first gene to j’s gene are swapped between C1 and C2; if 1/3 < b ≤ 2/3, all the genes from (j + 1)’s gene to k’s gene are swapped between the two chromosomes; otherwise, all the genes from (k + 1)’s gene to the last gene are swapped, and other substrings remain unchanged. Then, we generate two offspring chromosomes, C3 and C4. Figure 9(a) shows an illustration of the crossover procedure.Figure 9
An illustration of the genetic operation. (a) Is the two-point crossover operation. We generate a number that is larger than 1/3 and smaller than 2/3, and then, all the genes betweenj and k are swapped between the two parental chromosomes. (b) Is the one-point operation. We randomly choose the 3rd, 8th, and 12th genes as mutation objects. Because the randomly generated number for the first and the third objects are bigger than λ, we assign the value of their edge-neighbors’ genes, and when the generated number is smaller than λ for the second object, we assign one of its node-neighbors’ gene to its.
(a)(b)During mutation, given a parental chromosomeC5, we randomly generate a number x from 0 to N as the number of mutation objects, and then, we randomly choose x genes for the mutation operator. For each chosen gene gi, if a random number b is smaller than or equal to the weight of node-community λ, we randomly select one of i’s node-neighbors j and assign the community of j to gi; otherwise, we randomly choose one of i’s node-neighbors k and assign gk to gi. Then, we generate an offspring chromosome C5. An illustration of the one-point mutation is shown in Figure 9(b).


### 3.5. Local Search

To improve the accuracy and efficiency of the algorithm, we use a local search operation in MA-CD, as shown in Algorithm2. Given the best offspring chromosome derived by the genetic operation, we check each gene in the chromosome in a disorderly manner and judge whether assigning a neighbor’s value to it can lead to a higher modularity. If a generated random number c ≤ λ, one of the focal node’s node-neighbor communities is assigned to the gene; otherwise, we assign one of its edge-neighbor communities to it. If the new assignation can increase the modularity, then we will accept the new solution. The order of checking genes is set at random to eliminate endogeneity. Although the procedure may yield better performance by iterating it more times, the time complexity may be multiplied. Therefore, the operator is conducted for only one round for each iteration.Algorithm 2: Local search.
(1)
Load: the best offspring chromosome (Coffspring), number of nodes (N), and maximum number of communities (Cnum);(2)
Generate a sequence (Seq) with a disordered list from 1 to N;(3)
Fori = 1; i ≤ N; i++(4)
Coffspringnew (Seq(i)) = Coffspring (Seq(i));(5)
Generate a random numberc ranging from 0 to 1;(6)
ifc ≤ λ(7)
Find one ofSeq(i)’s node-neighbors x;(8)
Coffspringnew (Seq(i)) = Coffspring (x);(9)
If Modularity (Coffspringnew) > Modularity (Coffspring)(10)
Coffspring (Seq(i)) = Coffspring (x);(11)
End if(12)
else(13)
Find one ofSeq(i)’s edge-neighbors y;(14)
Coffspringnew (Seq(i)) = Coffspring (y);(15)
If Modularity (Coffspringnew) > Modularity (Coffspring)(16)
Coffspring (Seq(i)) = Coffspring (y);(17)
End if(18)
End if(19)
End for(20)
Output:Coffspring.


### 3.6. Complexity Analysis

In this section, we present an analysis of the time complexity of MA-CD. Given a network consisting ofN nodes and M edges, the time complexity of computing the modularity is ON2. For each loop, given the mating pool size MPs, the crossover and mutation operations are, respectively, run for MPs/2 times and MPs times at most. Because there are N genes in each chromosome, the time complexity of performing the genetic operation at each iteration is OMPs⋅N3. In the local search step, each gene is checked to judge whether the replacement of the value can lead to a better result, and thus, the local search at each iteration costs ON3. Because OMPs⋅N3>ON3, the time complexity of MA-CD is OMPs⋅N3.


## 3.1. Encoding and Decoding

The solution of community detection is encoded as a chromosome consisting of a list of genes:Chromosome=g1,g2,g3,…,gN, where the gene gi denotes the community node i belongs to. An illustration of the encoding is shown in Figure 7. Given a network consisting of 15 nodes, the initial chromosome {1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3} indicates that nodes 1–5 are assigned to the first community, nodes 6–10 are assigned to the second community, and nodes 11–15 are assigned to the third community. The 10th gene is changed from 2 to 1, and the 12th gene is changed from 3 to 2. Then, node 10 is dragged to community 1 from community 2, and node 12 is dragged to community 2 from community 3. When the procedure of the algorithm stops, we reversely decode the acquired chromosome as the solution of community detection.Figure 7
An illustration of the encoding. The upper part denotes two chromosomes consisting of genes, and the lower part denotes the solution of community detection corresponding to the two chromosomes. The solid lines denote positive edges, and the dashed lines denote negative edges. The different shapes of nodes denote the node attributes. The numbers next to nodes represent the node sequence number, and the dotted lines represent the community assignments.


## 3.2. Algorithm Framework

Algorithm1 shows the framework of MA-CD. We need to input the matrix of the signed network, the attribute for each node, and the necessary parameters. We first use the function “Initialization” to initialize a population P that consists of Ps chromosomes. These chromosomes can be decoded to the solutions of the community detection problem. Then, the procedure enters into a loop, where we use the function “tournament” to choose chromosomes with higher modularity as the parental population Parent. This operation involves running several “tournaments” among a few individuals chosen at random from the population. Individuals with better fitness have a higher probability of being chosen [59]. The number of selected parental chromosomes equals the size of the mating pool (MPs). The mating pool is formed by parental chromosomes that the selection operators deem to have higher fitness. Individuals can be repeatedly included in the mating pool so that individuals of higher fitness are more likely to be chosen multiple times [60]. In the next step, the population Parent is proceeded by the function “Genetic,” which includes both crossover and mutation operations, and then generates an offspring population offspring. Next, the function “Local” is used with offspring to find the local optimized chromosome opt. We then use the function “Update” to keep chromosomes with fitter solutions among P, Parent, offspring, and opt. The procedure may break the loop when the iteration reaches 1000 or the modularity of the best solution remains unchangeable over 50 iterations. Finally, we output the best solution of the community structure and its corresponding modularity.Algorithm 1: Framework of MA-CD.
(1)
Parameters: size of population (Ps), size of tournament (Ts), size of mating pool (MPs), maximum number of communities (Cnum), number of nodes (N), weight of node-community (λ), and probability of crossover (Cp);(2)
Input: the network matrix (A), the node attributes (V);(3)
P⟵ Initialization (A, V, Ps, Cnum, N, and λ);(4)
Repeat(5)
Parent⟵ Tournament (P, Ts, and MPs);(6)
Offspring⟵ Genetic (Parent, Cp, N, and λ);(7)
Opt⟵ Local (Offspring, N, and Cnum, λ);(8)
P⟵ Update (P, Parent, Offspring, and Opt);(9)
Until Termination(10)
Decode (P);(11)
Output: the fittest community assignation and its corresponding modularity.


## 3.3. Initialization

Before we introduce the initialization procedure, we present two definitions for different types of neighbors: (1) given a focal nodei, the edge neighbors of i are those nodes that positively connect with i; and (2) its node neighbors are those that share the same attribute with i.In the initialization, we generate a population withPs chromosomes. For each chromosome, we assign a random number “1, 2, 3, …, Cnum” to each gene as the community to which the node belongs. We then introduce a priori knowledge to speed up the convergence of the procedure and generate a random number a from 0 to 1 for each node i: if a is smaller than or equal to the weight of node-community λ, we randomly choose one of i’s node-neighbors k and assign k’s community number to i’s i.e.,gi=gk; otherwise, we randomly choose one of i’s edge neighbors l and make i’s community the same as l’s i.e.,gi=gl. An illustration of the prior knowledge is shown in Figure 8.Figure 8
An illustration of the initialization. Given the focal node 5, if the random numbera ≤ λ, we randomly choose its node-neighbor (node 4) and assign node 5 to community 2 (the community to which node 4 belongs); if a > λ, we assign community 1 to node 5 because its edge-neighbor node 2 belongs to community 1.


## 3.4. Genetic Operation

Genetic operation is the primary step of the genetic algorithm and includes both crossover and mutation operations. In this step, we perform a two-point crossover procedure and a one-point mutation procedure. According to the global framework (Algorithm1), the crossover procedure is conducted with the probability Cp, while the mutation procedure is conducted with the probability 1 − Cp.During crossover, given two parental chromosomesC1 and C2, we randomly choose two points j and k (j < k). If a randomly generated number b ≤ 1/3, then all the genes from the first gene to j’s gene are swapped between C1 and C2; if 1/3 < b ≤ 2/3, all the genes from (j + 1)’s gene to k’s gene are swapped between the two chromosomes; otherwise, all the genes from (k + 1)’s gene to the last gene are swapped, and other substrings remain unchanged. Then, we generate two offspring chromosomes, C3 and C4. Figure 9(a) shows an illustration of the crossover procedure.Figure 9
An illustration of the genetic operation. (a) Is the two-point crossover operation. We generate a number that is larger than 1/3 and smaller than 2/3, and then, all the genes betweenj and k are swapped between the two parental chromosomes. (b) Is the one-point operation. We randomly choose the 3rd, 8th, and 12th genes as mutation objects. Because the randomly generated number for the first and the third objects are bigger than λ, we assign the value of their edge-neighbors’ genes, and when the generated number is smaller than λ for the second object, we assign one of its node-neighbors’ gene to its.
(a)(b)During mutation, given a parental chromosomeC5, we randomly generate a number x from 0 to N as the number of mutation objects, and then, we randomly choose x genes for the mutation operator. For each chosen gene gi, if a random number b is smaller than or equal to the weight of node-community λ, we randomly select one of i’s node-neighbors j and assign the community of j to gi; otherwise, we randomly choose one of i’s node-neighbors k and assign gk to gi. Then, we generate an offspring chromosome C5. An illustration of the one-point mutation is shown in Figure 9(b).


## 3.5. Local Search

To improve the accuracy and efficiency of the algorithm, we use a local search operation in MA-CD, as shown in Algorithm2. Given the best offspring chromosome derived by the genetic operation, we check each gene in the chromosome in a disorderly manner and judge whether assigning a neighbor’s value to it can lead to a higher modularity. If a generated random number c ≤ λ, one of the focal node’s node-neighbor communities is assigned to the gene; otherwise, we assign one of its edge-neighbor communities to it. If the new assignation can increase the modularity, then we will accept the new solution. The order of checking genes is set at random to eliminate endogeneity. Although the procedure may yield better performance by iterating it more times, the time complexity may be multiplied. Therefore, the operator is conducted for only one round for each iteration.Algorithm 2: Local search.
(1)
Load: the best offspring chromosome (Coffspring), number of nodes (N), and maximum number of communities (Cnum);(2)
Generate a sequence (Seq) with a disordered list from 1 to N;(3)
Fori = 1; i ≤ N; i++(4)
Coffspringnew (Seq(i)) = Coffspring (Seq(i));(5)
Generate a random numberc ranging from 0 to 1;(6)
ifc ≤ λ(7)
Find one ofSeq(i)’s node-neighbors x;(8)
Coffspringnew (Seq(i)) = Coffspring (x);(9)
If Modularity (Coffspringnew) > Modularity (Coffspring)(10)
Coffspring (Seq(i)) = Coffspring (x);(11)
End if(12)
else(13)
Find one ofSeq(i)’s edge-neighbors y;(14)
Coffspringnew (Seq(i)) = Coffspring (y);(15)
If Modularity (Coffspringnew) > Modularity (Coffspring)(16)
Coffspring (Seq(i)) = Coffspring (y);(17)
End if(18)
End if(19)
End for(20)
Output:Coffspring.


## 3.6. Complexity Analysis

In this section, we present an analysis of the time complexity of MA-CD. Given a network consisting ofN nodes and M edges, the time complexity of computing the modularity is ON2. For each loop, given the mating pool size MPs, the crossover and mutation operations are, respectively, run for MPs/2 times and MPs times at most. Because there are N genes in each chromosome, the time complexity of performing the genetic operation at each iteration is OMPs⋅N3. In the local search step, each gene is checked to judge whether the replacement of the value can lead to a better result, and thus, the local search at each iteration costs ON3. Because OMPs⋅N3>ON3, the time complexity of MA-CD is OMPs⋅N3.


## 4. Numerical Simulation

To demonstrate the effectiveness and efficiency of the proposed modularity and the algorithm for detecting communities, we test the proposed results on computer-generated networks and real-world networks. We conduct the experiment on a computer with a 2.40 GHz CPU and 4.00 GB of RAM running Windows 10 with the proposed procedure written in MATLAB. Because the algorithm is not parameter-free, we set some values to the necessary parameters that ensure the excellent performance of the proposed algorithm, as shown in Table2. Specifically, a larger Ps or larger MPs help increases precision but sacrifice the time complexity. Therefore, we set Ps and MPs to moderate values (i.e., 100) that can produce a satisfactory solution in the memetic algorithm [46, 50, 51]. Ts is used to adjust the population diversity [59]. A smaller Ts suggests that weak individuals have a greater chance of being selected, thus increasing the population diversity. Therefore, Ts is set equal to 2, which is not a large number and has been proven to be efficient at promoting MA performance [46, 50, 51]. Cp is a parameter that adjusts the allocation between the long-distance search and the short-distance search. To find the optimum Cp, we run MA-CD on a computer-generated network and find that MA-CD performs best when Cp equals 0.2, as shown in Figure 10 in the appendix.Table 2
Parameter values in the algorithm.
ParametersMeaningsValuesPsSize of population100MPsSize of mating pool100TsSize of tournament2CpProbability of crossover0.2Figure 10
Mean value of the modularity result for different crossover probabilityCp for 10 runs. Different curves represent the results for λ = 0, 0.2, 0.4, 0.6, 0.8, and 1, respectively. The algorithm performs best when Cp equals 0.2.


### 4.1. Results for Benchmark Networks

We first run the proposed algorithm on a connected computer-generated network that is designed based on the benchmark proposed by Lancichinetti et al. [61] to test the effectiveness of community detection. We generate a network consisting of 128 nodes, where nodes 1–32, 33–64, 65–96, and 97–128 are, respectively, assigned to the node attributes “1,” “2,” “3,” and “4.” Nodes with the same attribute are connected by positive edges, while nodes with different attributes are connected by negative edges. The average degree for each node k is equal to 8, and the degrees for positive and negative edges k+ and k− equal 4. The network can thus be divided into four clusters (1–32, 33–64, 65–96, and 97–128), and the ideal community assignation should be equal to the four.We now present a comparison between the proposed algorithm and other methods. Among the classic algorithms that aim to detect communities based on the maximization of modularity, the genetic algorithm (GA) [41]; the greedy algorithm (GR) [51]; Blondel et al. ’s proposed algorithm (BA), which uses a two-step agglomerative process [39]; Clauset et al. ’s proposed algorithm (CA), which maximizes the modularity by aggregating iteratively connected communities [38]; and the typical Girvan’s and Newman’s proposed top-down dividing algorithm (NA) are the most popular algorithms [13]. Therefore, these studies compare the efficiency of MA-CD with the other five algorithms for community detection and are abbreviated as GA-CD, GR-CD, BA-CD, CA-CD, and NA-CD. Figure 11 shows the modularity result for each iteration. Generally, MA, GA, GR, and BA can acquire the same level of modularity, from which we can conclude that MA-CD is as effective as most heuristic algorithms. In the comparison of the speed of convergence, MA-CD performs the best due to the high efficiency of the local search operation.Figure 11
Modularity result for each iteration acquired by MA-CD, GA-CD, GR-CD, BA-CD, CA-CD, and NA-CD. (a), (b), (c), (d), (e), and (f) are the results forλ = 0, 0.2, 0.4, 0.6, 0.8, and 1, respectively. Each curve represents the error bar with the mean values +/− 1.96SEM.
(a)(b)(c)(d)(e)(f)To determine the effectiveness of the proposed modularity, we introduce a parameterω1 that represents the proportion of positive edges connecting two nodes with different attributes and negative edges connecting two nodes with the same attribute. We also introduce another parameter ω2 to represent the variation ratio of node attributes within the same cluster. ω1 denotes the decline of edge-community features because the number of positive edges between different communities and negative edges within the same community increases as ω1 increases; ω2 denotes the decline of node-community features because it generates a higher heterogeneity of node attributes within the same community.To evaluate the experimental result, we use the index of Normalized Mutual Information (NMI), which estimates the similarity between the original cluster assignation (1–32, 33–64, 65–96, and 97–128) and the detected communities [62]. NMI is the typical index for evaluating the effectiveness of the community-detection method [62] and is formulated as given in the following equation: (9)NMIA,B=−2∑i=1CA∑j=1CBCijlogCijn/Ci⋅C⋅j∑i=1CACi⋅logCi⋅/n+∑j=1CBC⋅jlogC⋅j/n,where A and B are two assignations between which the similarity is to be estimated; CA and CB are the number of clusters in assignations A and B, respectively; Cij denotes the number of nodes belonging to Cluster i in A that also belong to Cluster j in B; Ci⋅ and C⋅j are equal to the sum of the elements of Cij in Row i and Column j, respectively; and 0≤NMIA,B≤1, where a higher NMI (A, B) indicates a higher similarity between A and B.The 100-runs result of NMI between the original cluster assignation and the solution of community detection for differentλ and ω1 is shown in Figure 12. When the weight of node-community λ is small, NMI tends to decline as ω1 increases, while NMI remains equal to 1 for any value of ω1 when λ is large. A smaller λ is more sensitive to the feature of the edge-community structure, and thus, the smaller λ is capable of detecting the change in ω1. Conversely, a larger λ makes the procedure pay more attention to the node-community, and the solution is more likely to be parallel with the initial assignation of node attributes. Results show that the proposed method is effective at detecting both edge-community and node-community structures.Figure 12
Result of NMI for different settings ofλ and ω1. Each curve represents the error bar with the mean values +/− 1.96SEM.An experiment testing the effectiveness of detecting the node-community structure is also conducted. Figure13 shows the NMI result for different settings of λ and ω2 over 100 runs. Contrary to Figure 12, NMI remains equal to 1 when λ is small but decreases as ω2 increases when λ is large. Because λ denotes the weight of detecting the structure with node gathering and ω2 represents the reducing feature of the node-community structure, a larger λ is more sensitive to the change in ω2. Results thus demonstrate the effectiveness of the proposed method in catching the changed feature of the node attribute.Figure 13
Result of NMI for different settings ofλ and ω2. Each curve represents the error bar with the mean values +/− 1.96SEM.


### 4.2. Results for Real-World Networks

We then applied MA-CD, GA-CD, GR-CD, BA-CD, CA-CD, and NA-CD to 4 real-world networks: (1) the Slovene parliamentary party network (SPPN) is a network of 10 Slovene parliamentary parties set up by several experts on parliamentary activities [63]; (2) the social circle network (SCN) is a signed network consisting of 28 individuals of friends or enemies [64]; and (3) the Epidermal growth factor receptor network (EGFRN) is the pathway map of epidermal growth factor receptor with 330 nodes [65]; and the macrophage network (MN) is the molecular interaction map of a macrophage with 697 nodes [66]. All these networks are connected, and because the network data consisting of both edge attributes and node attributes are relatively few in the open source data, we subjectively assign a sequence of numbers to each node as the individual attribute. SPPN and SCN are typical signed networks that are used to study balance theory [46, 50, 51, 58]. Structural balance indicates that a network is balanced if it can be divided into two clusters where all the edges within clusters are positive while those between clusters are negative [67]. According to Sun et al. and Du et al., SPPN is nearly a balanced network because it can be classified as two opposed communities, where only two negative edges within Community 2 contribute to the structural imbalance, as shown in Figure 14 [50, 58]. SCN is a completely balanced network because it can be naturally divided into two opposed clusters of friends, as shown in Figure 15 [50, 58]. In this case, we use two methods of assigning the attribute to each node in SPPN and SCN: (1) we subjectively assign the node attribute based on the prior knowledge (PK) of structural balance (i.e., each node’s attribute equals its community number in Figures 14 and 15); and (2) we randomly assign each node a binary-attribute number. Because EGFRN and MN are relatively large in size compared with the other two, we randomly assign a 4-category attribute to each node, which is consistent with the setting in previous research [51]. Table 3 shows the numbers of nodes (N), node attributes (NA), edges (M), positive edges (M+), and negative edges (M−).Figure 14
Community assignations of SPPN-PK and SPPN-random. The solid lines denote positive edges, and the dashed lines denote negative edges. The different shapes of nodes denote the node attributes. The numbers next to nodes represent the node sequence number, and the dotted lines represent the community assignments. (a) Is the original network; (b) is the result of SPPN-PK; (c) is the result of SPPN-random withλ = 0, 0.2, and 0.4; (d) is the result of SPPN-random with λ = 0.6, 0.8, and 1.
(a)(b)(c)(d)Figure 15
Community assignations of SCN-PK and SCN-random. The solid lines denote positive edges, and the dashed lines denote negative edges. The different shapes of nodes denote the node attributes. The numbers next to nodes represent the node sequence number, and the dotted lines represent the community assignments. (a) Is the original network; (b) is the result of SCN-PK; (c) is the result of SCN-random withλ = 0, 0.2, and 0.4; (d) is the result of SCN -random with λ = 0.6, 0.8, and 1.
(a)(b)(c)(d)Table 3
Detailed information for the four real-world networks.
NetworksNNAMM+M−SPPN102451827SCN282423012EGFRN3304779515264MN69741425947478Table4 shows the results acquired by the six algorithms for different λ. The table shows that MA-CD performs the best, particularly on large-scale networks. Among the four networks, SPPN and SCN possess higher modularity because they are nearly fully balanced networks. EGFRN and MN have smaller modularity, which indicates that their features of community structure are relatively weak.Table 4
Modularity value and normalized value for differentλ on the real-world networks.
NetworksAlgorithmsλ = 0λ = 0.2λ = 0.4λ = 0.6λ = 0.8λ = 1QFQ^FQFQ^FQFQ^FQFQ^FQFQ^FQFQ^FSPPN-PKMA-CD0.4960.9920.4740.9480.4520.9040.4300.8600.4080.8160.3860.772GA-CD0.4960.9920.4740.9480.4520.9040.4300.8600.4080.8160.3860.772GR-CD0.4960.9920.4740.9480.4520.9040.4300.8600.4080.8160.3860.772BA-CD0.4960.9920.4740.9480.4520.9040.4300.8600.4080.8160.3860.772CA-CD0.3730.7460.3520.7040.3870.7740.3180.6350.3160.6330.3390.679NA-CD0.4960.9920.4740.9480.4520.9040.4300.8600.4080.8160.3860.772SPPN-randomMA-CD0.4960.9920.4210.8420.3450.6910.2700.5400.3100.6210.3860.772GA-CD0.4960.9920.4210.8420.3450.6910.2700.5400.3100.6210.3860.772GR-CD0.4960.9920.4210.8420.3450.6910.2700.5400.3100.6210.3860.772BA-CD0.4960.9920.4210.8420.3450.6910.2700.5400.2430.4850.2460.492CA-CD0.3420.6830.3240.6480.3070.6140.2220.4440.2510.5030.3040.609NA-CD0.4960.9920.4210.8420.3450.6910.2700.5400.3100.6210.3860.772SCN-PKMA-CD0.4990.9980.4880.9760.4760.9520.4290.8590.4020.8040.3740.749GA-CD0.4990.9980.4880.9760.4760.9520.4290.8590.4020.8040.3740.749GR-CD0.4990.9980.4880.9760.4760.9520.4290.8590.4020.8040.3740.749BA-CD0.4350.8700.3830.7670.4540.9080.4190.8370.3610.7230.3040.608CA-CD0.3920.7830.3580.7150.2650.5310.2470.4950.2610.5220.2110.423NA-CD0.0260.0520.4840.9690.4570.9140.4290.8590.4020.8040.3740.749SCN-randomMA-CD0.4990.9980.4360.8710.3590.7190.2830.5660.2800.5600.3510.703GA-CD0.4990.9980.4360.8710.3590.7190.2830.5660.2800.5600.3510.703GR-CD0.4990.9980.4360.8710.3590.7190.2830.5660.2800.5600.3510.703BA-CD0.4450.8900.3580.7150.3380.6750.2830.5710.2080.4150.1480.297CA-CD0.4000.8000.3030.6060.2000.4010.1690.3380.1700.3400.2070.414NA-CD0.0260.0520.4360.8710.3590.7190.2670.5350.2800.5600.3510.703EGFRNMA-CD0.3060.3790.2870.3530.2520.3060.2260.2690.2790.3190.3440.393GA-CD0.2760.3420.2170.2660.1790.2160.1630.1930.2470.2850.3440.393GR-CD0.2920.3620.2790.3430.2460.2990.2220.2650.2790.3190.3440.393BA-CD0.3000.3720.2810.3450.2580.3140.2370.2830.2140.2510.1930.220CA-CD0.0470.0580.0810.0970.1010.1180.1310.1510.1610.1850.1980.226NA-CD0.2460.3050.2320.2850.2190.2650.1950.2320.2210.2550.3040.347MNMA-CD0.3290.4080.3110.3830.2680.3260.2390.2860.2760.3160.3440.393GA-CD0.2840.3530.2040.2500.1650.1990.1560.1840.2030.2330.3440.393GR-CD0.3160.3930.3040.3750.2630.3200.2320.2770.2760.3160.3440.393BA-CD0.3290.4080.3030.3720.2780.3380.2470.2950.2180.2560.1900.217CA-CD0.0170.0210.0510.0600.0880.1010.1200.1380.1550.1780.1910.218NA-CD0.2820.3500.2550.3140.2210.2690.2080.2490.2210.2550.2890.330In the proposed algorithm, each solution can be decoded as a community assignation. Figures14 and 15 show the results of community assignments in SPPN and SCN, respectively. In SPPN, Figure 14 is the result of SPPN-PK, where the node attribute equals the community assignation based on balance theory, and the proposed algorithm can quickly catch the specific feature. In SPPN-random, the proposed method can find the best solution of the edge-community structure when λ is small, as shown in Figure 14. In this structure, only two edges (marked by rhombuses) do not comply with the rule of edge-community structure according to Gómez et al. [47]. The result is consistent with the result of clustering assignation in computing global structural balance [58], which indicates that the proposed method can also be applied to the detection of structural balance. When λ increases, the proposed method can detect the node-community feature where nodes with the same attribute are assigned to the same community, as shown in Figure 13(d).Because SCN is a balanced network and the node attributes are also subjectively assigned to the same community assignment based on prior knowledge, the fully signed SCN-PK complies with both the rules of edge-community and node-community structures [46, 50, 51]. The community assignation of SCN-PK in Figure 15 is the optimal result for any λ. When each node attribute is randomly assigned, the results vary with different λ. A smaller λ helps detect the edge-community structure (Figure 15) while a larger λ aides finding the node-community structure (Figure 15). Experiments show that the newly proposed modularity and the corresponding optimization algorithm are valid when detecting the community structure in fully signed networks.


## 4.1. Results for Benchmark Networks

We first run the proposed algorithm on a connected computer-generated network that is designed based on the benchmark proposed by Lancichinetti et al. [61] to test the effectiveness of community detection. We generate a network consisting of 128 nodes, where nodes 1–32, 33–64, 65–96, and 97–128 are, respectively, assigned to the node attributes “1,” “2,” “3,” and “4.” Nodes with the same attribute are connected by positive edges, while nodes with different attributes are connected by negative edges. The average degree for each node k is equal to 8, and the degrees for positive and negative edges k+ and k− equal 4. The network can thus be divided into four clusters (1–32, 33–64, 65–96, and 97–128), and the ideal community assignation should be equal to the four.We now present a comparison between the proposed algorithm and other methods. Among the classic algorithms that aim to detect communities based on the maximization of modularity, the genetic algorithm (GA) [41]; the greedy algorithm (GR) [51]; Blondel et al. ’s proposed algorithm (BA), which uses a two-step agglomerative process [39]; Clauset et al. ’s proposed algorithm (CA), which maximizes the modularity by aggregating iteratively connected communities [38]; and the typical Girvan’s and Newman’s proposed top-down dividing algorithm (NA) are the most popular algorithms [13]. Therefore, these studies compare the efficiency of MA-CD with the other five algorithms for community detection and are abbreviated as GA-CD, GR-CD, BA-CD, CA-CD, and NA-CD. Figure 11 shows the modularity result for each iteration. Generally, MA, GA, GR, and BA can acquire the same level of modularity, from which we can conclude that MA-CD is as effective as most heuristic algorithms. In the comparison of the speed of convergence, MA-CD performs the best due to the high efficiency of the local search operation.Figure 11
Modularity result for each iteration acquired by MA-CD, GA-CD, GR-CD, BA-CD, CA-CD, and NA-CD. (a), (b), (c), (d), (e), and (f) are the results forλ = 0, 0.2, 0.4, 0.6, 0.8, and 1, respectively. Each curve represents the error bar with the mean values +/− 1.96SEM.
(a)(b)(c)(d)(e)(f)To determine the effectiveness of the proposed modularity, we introduce a parameterω1 that represents the proportion of positive edges connecting two nodes with different attributes and negative edges connecting two nodes with the same attribute. We also introduce another parameter ω2 to represent the variation ratio of node attributes within the same cluster. ω1 denotes the decline of edge-community features because the number of positive edges between different communities and negative edges within the same community increases as ω1 increases; ω2 denotes the decline of node-community features because it generates a higher heterogeneity of node attributes within the same community.To evaluate the experimental result, we use the index of Normalized Mutual Information (NMI), which estimates the similarity between the original cluster assignation (1–32, 33–64, 65–96, and 97–128) and the detected communities [62]. NMI is the typical index for evaluating the effectiveness of the community-detection method [62] and is formulated as given in the following equation: (9)NMIA,B=−2∑i=1CA∑j=1CBCijlogCijn/Ci⋅C⋅j∑i=1CACi⋅logCi⋅/n+∑j=1CBC⋅jlogC⋅j/n,where A and B are two assignations between which the similarity is to be estimated; CA and CB are the number of clusters in assignations A and B, respectively; Cij denotes the number of nodes belonging to Cluster i in A that also belong to Cluster j in B; Ci⋅ and C⋅j are equal to the sum of the elements of Cij in Row i and Column j, respectively; and 0≤NMIA,B≤1, where a higher NMI (A, B) indicates a higher similarity between A and B.The 100-runs result of NMI between the original cluster assignation and the solution of community detection for differentλ and ω1 is shown in Figure 12. When the weight of node-community λ is small, NMI tends to decline as ω1 increases, while NMI remains equal to 1 for any value of ω1 when λ is large. A smaller λ is more sensitive to the feature of the edge-community structure, and thus, the smaller λ is capable of detecting the change in ω1. Conversely, a larger λ makes the procedure pay more attention to the node-community, and the solution is more likely to be parallel with the initial assignation of node attributes. Results show that the proposed method is effective at detecting both edge-community and node-community structures.Figure 12
Result of NMI for different settings ofλ and ω1. Each curve represents the error bar with the mean values +/− 1.96SEM.An experiment testing the effectiveness of detecting the node-community structure is also conducted. Figure13 shows the NMI result for different settings of λ and ω2 over 100 runs. Contrary to Figure 12, NMI remains equal to 1 when λ is small but decreases as ω2 increases when λ is large. Because λ denotes the weight of detecting the structure with node gathering and ω2 represents the reducing feature of the node-community structure, a larger λ is more sensitive to the change in ω2. Results thus demonstrate the effectiveness of the proposed method in catching the changed feature of the node attribute.Figure 13
Result of NMI for different settings ofλ and ω2. Each curve represents the error bar with the mean values +/− 1.96SEM.


## 4.2. Results for Real-World Networks

We then applied MA-CD, GA-CD, GR-CD, BA-CD, CA-CD, and NA-CD to 4 real-world networks: (1) the Slovene parliamentary party network (SPPN) is a network of 10 Slovene parliamentary parties set up by several experts on parliamentary activities [63]; (2) the social circle network (SCN) is a signed network consisting of 28 individuals of friends or enemies [64]; and (3) the Epidermal growth factor receptor network (EGFRN) is the pathway map of epidermal growth factor receptor with 330 nodes [65]; and the macrophage network (MN) is the molecular interaction map of a macrophage with 697 nodes [66]. All these networks are connected, and because the network data consisting of both edge attributes and node attributes are relatively few in the open source data, we subjectively assign a sequence of numbers to each node as the individual attribute. SPPN and SCN are typical signed networks that are used to study balance theory [46, 50, 51, 58]. Structural balance indicates that a network is balanced if it can be divided into two clusters where all the edges within clusters are positive while those between clusters are negative [67]. According to Sun et al. and Du et al., SPPN is nearly a balanced network because it can be classified as two opposed communities, where only two negative edges within Community 2 contribute to the structural imbalance, as shown in Figure 14 [50, 58]. SCN is a completely balanced network because it can be naturally divided into two opposed clusters of friends, as shown in Figure 15 [50, 58]. In this case, we use two methods of assigning the attribute to each node in SPPN and SCN: (1) we subjectively assign the node attribute based on the prior knowledge (PK) of structural balance (i.e., each node’s attribute equals its community number in Figures 14 and 15); and (2) we randomly assign each node a binary-attribute number. Because EGFRN and MN are relatively large in size compared with the other two, we randomly assign a 4-category attribute to each node, which is consistent with the setting in previous research [51]. Table 3 shows the numbers of nodes (N), node attributes (NA), edges (M), positive edges (M+), and negative edges (M−).Figure 14
Community assignations of SPPN-PK and SPPN-random. The solid lines denote positive edges, and the dashed lines denote negative edges. The different shapes of nodes denote the node attributes. The numbers next to nodes represent the node sequence number, and the dotted lines represent the community assignments. (a) Is the original network; (b) is the result of SPPN-PK; (c) is the result of SPPN-random withλ = 0, 0.2, and 0.4; (d) is the result of SPPN-random with λ = 0.6, 0.8, and 1.
(a)(b)(c)(d)Figure 15
Community assignations of SCN-PK and SCN-random. The solid lines denote positive edges, and the dashed lines denote negative edges. The different shapes of nodes denote the node attributes. The numbers next to nodes represent the node sequence number, and the dotted lines represent the community assignments. (a) Is the original network; (b) is the result of SCN-PK; (c) is the result of SCN-random withλ = 0, 0.2, and 0.4; (d) is the result of SCN -random with λ = 0.6, 0.8, and 1.
(a)(b)(c)(d)Table 3
Detailed information for the four real-world networks.
NetworksNNAMM+M−SPPN102451827SCN282423012EGFRN3304779515264MN69741425947478Table4 shows the results acquired by the six algorithms for different λ. The table shows that MA-CD performs the best, particularly on large-scale networks. Among the four networks, SPPN and SCN possess higher modularity because they are nearly fully balanced networks. EGFRN and MN have smaller modularity, which indicates that their features of community structure are relatively weak.Table 4
Modularity value and normalized value for differentλ on the real-world networks.
NetworksAlgorithmsλ = 0λ = 0.2λ = 0.4λ = 0.6λ = 0.8λ = 1QFQ^FQFQ^FQFQ^FQFQ^FQFQ^FQFQ^FSPPN-PKMA-CD0.4960.9920.4740.9480.4520.9040.4300.8600.4080.8160.3860.772GA-CD0.4960.9920.4740.9480.4520.9040.4300.8600.4080.8160.3860.772GR-CD0.4960.9920.4740.9480.4520.9040.4300.8600.4080.8160.3860.772BA-CD0.4960.9920.4740.9480.4520.9040.4300.8600.4080.8160.3860.772CA-CD0.3730.7460.3520.7040.3870.7740.3180.6350.3160.6330.3390.679NA-CD0.4960.9920.4740.9480.4520.9040.4300.8600.4080.8160.3860.772SPPN-randomMA-CD0.4960.9920.4210.8420.3450.6910.2700.5400.3100.6210.3860.772GA-CD0.4960.9920.4210.8420.3450.6910.2700.5400.3100.6210.3860.772GR-CD0.4960.9920.4210.8420.3450.6910.2700.5400.3100.6210.3860.772BA-CD0.4960.9920.4210.8420.3450.6910.2700.5400.2430.4850.2460.492CA-CD0.3420.6830.3240.6480.3070.6140.2220.4440.2510.5030.3040.609NA-CD0.4960.9920.4210.8420.3450.6910.2700.5400.3100.6210.3860.772SCN-PKMA-CD0.4990.9980.4880.9760.4760.9520.4290.8590.4020.8040.3740.749GA-CD0.4990.9980.4880.9760.4760.9520.4290.8590.4020.8040.3740.749GR-CD0.4990.9980.4880.9760.4760.9520.4290.8590.4020.8040.3740.749BA-CD0.4350.8700.3830.7670.4540.9080.4190.8370.3610.7230.3040.608CA-CD0.3920.7830.3580.7150.2650.5310.2470.4950.2610.5220.2110.423NA-CD0.0260.0520.4840.9690.4570.9140.4290.8590.4020.8040.3740.749SCN-randomMA-CD0.4990.9980.4360.8710.3590.7190.2830.5660.2800.5600.3510.703GA-CD0.4990.9980.4360.8710.3590.7190.2830.5660.2800.5600.3510.703GR-CD0.4990.9980.4360.8710.3590.7190.2830.5660.2800.5600.3510.703BA-CD0.4450.8900.3580.7150.3380.6750.2830.5710.2080.4150.1480.297CA-CD0.4000.8000.3030.6060.2000.4010.1690.3380.1700.3400.2070.414NA-CD0.0260.0520.4360.8710.3590.7190.2670.5350.2800.5600.3510.703EGFRNMA-CD0.3060.3790.2870.3530.2520.3060.2260.2690.2790.3190.3440.393GA-CD0.2760.3420.2170.2660.1790.2160.1630.1930.2470.2850.3440.393GR-CD0.2920.3620.2790.3430.2460.2990.2220.2650.2790.3190.3440.393BA-CD0.3000.3720.2810.3450.2580.3140.2370.2830.2140.2510.1930.220CA-CD0.0470.0580.0810.0970.1010.1180.1310.1510.1610.1850.1980.226NA-CD0.2460.3050.2320.2850.2190.2650.1950.2320.2210.2550.3040.347MNMA-CD0.3290.4080.3110.3830.2680.3260.2390.2860.2760.3160.3440.393GA-CD0.2840.3530.2040.2500.1650.1990.1560.1840.2030.2330.3440.393GR-CD0.3160.3930.3040.3750.2630.3200.2320.2770.2760.3160.3440.393BA-CD0.3290.4080.3030.3720.2780.3380.2470.2950.2180.2560.1900.217CA-CD0.0170.0210.0510.0600.0880.1010.1200.1380.1550.1780.1910.218NA-CD0.2820.3500.2550.3140.2210.2690.2080.2490.2210.2550.2890.330In the proposed algorithm, each solution can be decoded as a community assignation. Figures14 and 15 show the results of community assignments in SPPN and SCN, respectively. In SPPN, Figure 14 is the result of SPPN-PK, where the node attribute equals the community assignation based on balance theory, and the proposed algorithm can quickly catch the specific feature. In SPPN-random, the proposed method can find the best solution of the edge-community structure when λ is small, as shown in Figure 14. In this structure, only two edges (marked by rhombuses) do not comply with the rule of edge-community structure according to Gómez et al. [47]. The result is consistent with the result of clustering assignation in computing global structural balance [58], which indicates that the proposed method can also be applied to the detection of structural balance. When λ increases, the proposed method can detect the node-community feature where nodes with the same attribute are assigned to the same community, as shown in Figure 13(d).Because SCN is a balanced network and the node attributes are also subjectively assigned to the same community assignment based on prior knowledge, the fully signed SCN-PK complies with both the rules of edge-community and node-community structures [46, 50, 51]. The community assignation of SCN-PK in Figure 15 is the optimal result for any λ. When each node attribute is randomly assigned, the results vary with different λ. A smaller λ helps detect the edge-community structure (Figure 15) while a larger λ aides finding the node-community structure (Figure 15). Experiments show that the newly proposed modularity and the corresponding optimization algorithm are valid when detecting the community structure in fully signed networks.


## 5. Conclusion

This study discusses community structure in fully signed networks and notes its social significance for computational social science. We propose a generalized modularity to measure the feature of community structure based on the classic modularity proposed by Newman and Girvan [18] and its variant proposed by Gómez et al. [47]. The proposed modularity can capture both the change in edge-community and node-community features, which makes up for the defect of insufficient discussion on node attributes. In the field of computational social science, the analysis of node attributes has gradually become more important because it is the basic element of the network system [1, 51]. Due to homophily and social influence, nodes and edges are dependent on each other [68, 69]. This study recognizes the distinct roles of nodes and edges in forming social communities, which is a prospective methodological study aimed at promoting research on fully signed networks [46, 50, 51]. The proposed method can be applied to compute the level of structural balance because the proposed modularity includes the ideas of balance theory. The index can also be extended to detect signed networks characterized by nonbinary edges.To detect potential communities, we propose a memetic algorithm (MA) that maximizes the generalized modularity. We present a comparison of MA and some classic modularity-maximization-based algorithms (GA [41], GR [51], BA [39], CA [38], and NA [13]), and experiments show that the proposed method can best optimize the objective function and realize effective community detection.This study opens up the possibility of providing a normative tool by which to analyze community structure when edge signs and node attributes are considered, which provides a good path to extend theories in computational social science. For example, individual attributes and social relations are both focused on in the research of collective action or political polarization, while the proposed method can help researchers quickly find the potential communities among investigation samples.In social network analysis, it is common to explore both network relationships and demographic variables [51]. Given three basic network elements (node, edge, and network structure), Du and He proposed three gathering modes for social collective behaviors, as shown in Figure 16 [70]. The homophily rule lays a theoretical basis for node gathering, where people with the same attributes gather together and form segregation from the global view [48]. Balance theory explains the edge gathering where the crowd is classified into multiple opposing groups of friends [53]. Studies of community structure or cohesive subgroups explain the structural gathering where relationships within communities are denser than those between communities [15]. The proposed model developed in this study includes all three gathering modes, and this study provides an opportunity to explore the relationship between individual behaviors and collective behaviors.Figure 16
Social significance of this study in explaining collective behaviors.However, some limitations remain that need to be mitigated in future research. The proposed method may sometimes fall into local optimism, and a more intelligent algorithm should be designed to solve the community detection problem. On the other hand, the node-community and the edge-community are set in a unified objective function; thus, one of the future works is to use a multiobjective optimization algorithm to explore the community structure. Future research may also apply the proposed method to more social networks that contain both node and edge attributes. Despite these limitations, this study is one of the few to explore the community structure in fully signed networks, which contributes to a better understanding of complex systems.



---

*Source: 8767131-2023-02-24.xml*