A Novel Community Detection Method of Social Networks for the Well-Being of Urban Public Spaces

Abstract

A third place (public social space) has been proven to be a gathering place for communities of friends on social networks (social media). The regulars at places of worship, cafes, parks, and entertainment can also possibly be friends with those who follow each other on social media, with other non-regulars being social network friends of one of the regulars. Therefore, detecting and analyzing user-friendly communities on social networks can provide references for the layout and construction of urban public spaces. In this article, we focus on proposing a method for detecting communities of signed social networks and mining $\gamma$-Quasi-Cliques for closely related users within them. We fully consider the relationship between friends and enemies of objects in signed networks, consider the mutual influence between friends or enemies, and propose a novel method to recompute the weighted edges between nodes and mining $\gamma$-Quasi-Cliques. In our experiment, with a variety of thresholds given, we conducted multiple sets of tests via real-life social network datasets, compared various reweighted datasets, and detected maximal balanced $\gamma$-Quasi-Cliques to determine the optimal parameters of our method.

1. Introduction

In community building, the third place [1] is the social public place separate from home (“first place”) and the workplace (“second place”). It is a public place where people easily visit and communicate with friends; especially, its functional role can be revealed by the structures of the representative friendship circles in social networks [2]. Usually, third places include some public spaces such as churches, cafes, clubs, public libraries, operas, parks, monuments, restaurants, or indoor recreation. The study in Reference [2] suggests that each friendship community may indicate whether the type of third place is more suitable for the existing friendship circle, or larger communities can be constructed by analyzing and bridging the differences between strangers. At the same time, some users may overlap in different communities, indicating that they have a wider social behavior or are regular individuals in certain kinds of public spaces, while other non-regular users may visit these third places because of their regular friends.

In order to make some reasonable suggestions for land planning and public space distribution, it is of great significance to detect friendship communities in social networks. To solve this problem, this paper intends to propose an algorithm to detect friend/enemy communities effectively in signed social networks. Therefore, we use graph theory to solve this problem.

Graph theory [3] is a branch of mathematics that treats a graph as the research object and has a wide range of applications in the existing research, including biology, computers, social systems, and other fields such as protein interaction network analysis, genetic biology network analysis, web community mining, social network analysis, and knowledge graph construction [4,5]. In addition, recently, the graph mining technique in the social network has been considered as an important research direction in the data field. A graph in graph theory is composed of several given nodes and edges, and the edges connect certain nodes. A graph is usually used to describe the specific relationship between particular objects. For example, a node is used to represent a user in the social network; an edge is utilized to connect two users, indicating a relationship between the corresponding ones.

Typically, nodes in a network represent individuals, while edges represent the relationships between them. In the regular setting, only positive relations representing proximity or similarity are considered. However, when the network has like/dislike, love/hate, respect/disrespect, or trust/distrust relationships, such a representation, with only a positive edge, is not enough, since it cannot encode the sign of the relationship. These networks can be modeled as the signed social networks, where edge weights can be positive or negative. Early use of signed networks can be found in anthropology, where negative edges were used to represent antagonistic relationships between tribes. In earlier years, signed social networks were used in anthropology, where negative edges were used to denote negative relations such as tribal hostility [6]. In the field of computer science, there is a lot of research on signed social networks, for example, Silviu built a signed network for Wikipedia [7], Liu et al. Al proposed a link prediction method for a signed social network [8], and Timo presented a model for creating signed networks enabling friends profit from enemies [9].

The most common theory associated with signed social networks is the “social balance theory”, which intuitively can be interpreted as “my friend’s friend is my friend”, “my friend’s enemy is my enemy”, “my enemy’s friend is my enemy”, and “my enemy’s enemy is my friend”. Below, we present a definition, in that a graph is balanced if any part of the graph does not conflict with the “social balance theory”.

Figure 1 illustrates the “social balance theory”, where the signed “+” denotes “friend”/“positive”/“trust” and “−” denotes “enemy”/“negative”/“distrust”, subgraphs (a) and (b) are balanced, and (c) and (d) are unbalanced.

References [10,11] show that networks following the concept of balance can cluster into two perfect adversarial groups. In our previous work [12], we also proposed a detection method for maximal balanced cliques in the signed social networks based on the balance theory. A clique is a completely connected subgraph of a graph, which requires all nodes in the subgraph to be connected in pairs with strict constraints. Sometimes, an important node in the dataset has missing pieces of information, which connect it with other nodes, or there is no edge between it and an irrelevant node. As the conditions of clique detection are too strict, this important node is easy to be ignored or is pruned in the process of clique detection [13]. The $\gamma$-Quasi-Cliques have the capacity to solve the mentioned-above problems, as they have more relaxing conditions in comparison to the clique [14].

In this paper, we propose a new model to detect $\gamma$-Quasi-Cliques (it is possible to include the negative edges) for the signed social network, and considering “friendly density” and mutual influence with friends and enemies, we use a method to recompute the weight of edges in the signed social network.

The organizational structure of this paper is: Section 1 introduces the signed social networks and social balanced theory; Section 2 presents related works and analyzes the clustering method for the signed social network in the existing research work; Section 3 explains the basic knowledge about the “friendly density theory” and signed social network and introduces a way to recompute the weight of edges in the signed network and the maximal balanced $\gamma$-Quasi-Clique detect method; Section 4 applies the famous open datasets on our model in the experiment, and determines the optimal threshold for filtering the recomputed weight adjacency matrix and the best value of γ. Finally, Section 5 presents the conclusion of the work and further stages of the research.

2. Related Works

Signed social networks with positive and negative links have attracted considerable attention over the past few years. One of the main challenges in signed network analysis is community detection, which aims to find mutually opposing groups with two characteristics: (1) entities within the same group have as many positive relationships as possible; (2) entities between different groups have as many negative relationships as possible.

The majority of existing algorithms for community detection in signed networks aim to provide hard partitioning of the network, where any node should belong to a single community, such as cliques [15]. However, overlapping communities, in which a node is allowed to belong to multiple communities, are widespread in many real-world networks. Another disadvantage of some existing algorithms is that the final number of clusters k should be the input to the clustering process. However, it may be the case that we do not know k in advance. It will have the limitation of detecting communities by giving clusters the number k.

However, the clustering algorithm of a signed social network cannot succeed to obtain the results only by directly extending the theory and algorithm of the unsigned social network. When edge weights are allowed to be negative, many unsigned social network concepts and algorithms collapse, because they do not work properly in this situation. More recently, studies have been conducted to develop algorithms for efficient methods of clustering signed networks. Doreian and Mrvar [16] proposed a local search strategy similar to Kernighan-Lin algorithm. Yang et al. [17] proposed an agent-based approach, which is essentially a random walk on a graph. Anchuri and Magdon-Ismail1 proposed a hierarchical iterative approach to solve two-way frustrations and signed modularity using spectrum relaxation targets at each level. Bansal et al. [18] also considered the problem of signed graph clustering, although their formula is driven by correlation clustering. They proposed two approximation algorithms and proved the approximation bounds.

Renjie et al. [19] proposed a model, named stable k-core, to measure the stability of a community in signed graphs. Chengyi et al. [20] gave an improved modularity function for signed networks on the basis of the existing modularity function and devised a new community detection algorithm for signed networks. Cadena et al. [21] extended the concept of subgraph density to detect events in signed networks. Ref. [22] is devoted to the study of influence diffusion in signed networks and studies the process of influence diffusion in signed networks. In [23], Tsourakakis et al. considered dense graph detection problems with negative weights. Ordozgoiti et al. [24] proposed a more efficient and scalable approach to this problem.

Qi et al. [25] proposed a framework to solve the problem of negative weights in the signed social networks. In the first step, the authors defined a new computation process to compute the weights between two nodes. They combined the negative edges with the positive ones directly into a parameter called “friendly density”. The proposal of this definition becomes a great contribution to the more objective and reasonable recomputation of edge weights. This paper refers to the definition of friend density to recompute the weights of edges in the next section. Moreover, utilizing the mentioned definition, we consider the six-dimensional space theory [26] to further reasonably compute and obtain a new weight adjacency matrix.

3. Basic Notions and Approach

3.1. Terminologies and Notations

3.1.1. Recalculate the Weights between Friends

A signed social network graph can be noted as G = (V, E, W), where V is a set of nodes, E is a set of weights edges that represents the relationships between the nodes, W is the weight on every edge e, the adjacency matrix A is defined as follows:

$$\mathrm{A}=\{\begin{array}{c}\left|w\left(e\right)\right|, if e\left(v_i, v_j\right)is positive\\ -\left|w\left(e\right)\right|, if e\left(v_i, v_j\right) is negative \\ 0, if \left(v_i, v_j\right) is unknown\end{array}$$

(1)

For a network G with only positive edges, clustering can be seen as a process that detects all dense subgraphs in G [25]. The computation of dense subgraph C is defined by:

$$d\left(G^{\prime }\right)=\frac{2{{\displaystyle \sum }}_{e\in E\left(G^{\prime }\right)}w\left(e\right)}{\left|V\left(G^{\prime }\right)\right|\left|V\left(G^{\prime }\right)-1\right|}.$$

(2)

When the G’ is a subgraph of G, w(e) is the weight of edge e in E(G’), |·| is the absolute value of the number. Equation (2) can be generalized to a singed graph where w(e) can be negative. The density of the graph will drop or rise by adding new negative or positive edges.

In a signed network, the relationship between two nodes (i.e., the weights of the edges) may be influenced by rumors/personal bias and may be negative and close to 0, and that negative relationship is subjective and one-sided. When both nodes have positive relationships with their mutual friends, that negative edge is easily influenced by the mutual influence of the friends’ positive relationship. In order to avoid such assertive positive/negative edges caused by considering only the relationship between two nodes, and to better cluster the friendly density clusters, we plan to consider the true state of two nodes based on a more “global” structural environment and adjust their pre-existing or given relationships as necessary. Therefore, we recalculate the relationship weights between two nodes considering the global structural environment and redefine their positive/negative relationship by a reasonable threshold (the selection of the threshold is explored in Section 4 in order not to destroy the original network structure as much as possible).

To solve this problem, reference [25] introduces a weight-completing method, according to which we will obtain the different weights ${\beta }_{\zeta }$ based on length ζ of the path $P_{\zeta }$.

$$w_{u,v}={\displaystyle \sum }_{\zeta =1}^k[{\beta }_{\zeta }\ast {\displaystyle \sum }_{PϵP_{\zeta }}{\displaystyle \prod }_{eϵP}w\left(e\right)]$$

(3)

Among them, $\zeta$ represents the path length, $k$ is the maximum value of the path length $\zeta$, the formula traverses all paths of the path length $\zeta \in \left[1,k\right]$, and for each path $P$, the multiplication of the weights $w_{u,v}$ of each edge $e$ on the path $P$ is calculated. If there are multiple paths $P$ of the same length $\zeta$, find the sum of their concatenated products.

Figure 2 shows an example to explain it. There are three paths between nodes u and v, and the value of each edge represents the positive/negative relationship and weight between the two nodes. When we consider each path equally, ${\beta }_{\zeta }$ = 1, and according to Equation (3), the predicted weight of $w_{u,v}$ is

$$w_{u,v}=0.3-0.5\times 0.1-0.5\times 0.3\times 0.1=0.235$$

If we use the decaying function ${\beta }_{\zeta }=\frac{1}{\zeta !}$, then the predicted weight of $w_{u,v}$ is

$$w_{u,v}=0.3-\frac{0.5\times 0.1}{2!}-\frac{0.5\times 0.3\times 0.1}{3!}=0.2725$$

Comparing the two $w_{u,v}$, when we choose decaying function ${\beta }_{\zeta }=\frac{1}{\zeta !}$, the positive relationship between u and v becomes more evident. Similarly, through the calculation of Equation (3), the weight of the negative edge may be more negative.

We give an example below to calculate the new relationship value under the mutual influences of common friends even if the direct relationship between nodes u and v is negative, taking into account reasons such as rumors or personal biases: even their direct relationship is negative, and they should gather together in the same cluster. In the example, we choose ${\beta }_{\zeta }=\frac{1}{\zeta !} as the$decaying function. The original graph of this example is shown as Figure 3.

Example:

$$w_{u,v}=-0.1+\frac{0.4\times 0.8}{2!}-\frac{0.7\times 0.9}{2!}=0.375$$

After recalculating the weights between nodes u, v, the network is updated to Figure 4. It is obvious that the network becomes a balanced network, which can be detected in the next step of the balanced community detection algorithm. At this time, the relationship between u and v changes from negative to positive, which is an important reason to use common friends/enemies as parameters for weight calculation. This step can as far as possible avoid the influence of rumors, personal biases, or noisy data collection, and is more comprehensive consider the relationship between two nodes.

However, the process of enumerating all paths for a pair of nodes is NP-hard. To solve the issue, Qi [25] advocates using the (u, v) element in the matrix $A^{\zeta }$ ($\zeta power of A$), which is equal to the sum of the weights of all paths of length $\zeta$ between u and v.

$$w_{u,v}={\displaystyle \sum }_{\zeta =1}^{\infty }[{\beta }_{\zeta }\cdot {\left(A^{\zeta }\right)}_{u, v}]$$

(4)

3.1.2. γ-Quasi-Cliques

After completing the graph with the weight of edges in the signed social network, the next step is to detect the $\gamma$-Quasi-Cliques ($\gamma$ is a user-given parameter through which the detection conditions of the Quasi-Cliques can be adjusted. Definition 1 will give a detailed description).

In our previous work [13], we proposed and implemented an enumeration method based on FCA [27,28] for clustering the $\gamma$-Quasi-Cliques. in the social network. This method is suitable for the unsigned graph. Hence, we have to optimize this method to utilize it in the signed social network graph.

Definition 1 ($\mathbf{\gamma }$-Quasi-Cliques) [13].

Given a graph G and$G=\left(V, E\right)$, if$\forall v\in V, de{g}^G\left(v\right)\ge \gamma \left(\left|V\right|-1\right)$, then the graph G is a Quasi-Cliques and the parameter is$\gamma$(given by users), by$\gamma$-Quasi-Cliques. When V is the set of nodes and$V=\left\{v_1, v_2, v_3, \dots , v_n\right\}$, E is the set of edges and$E=\left\{\left(u, v\right)\right| u,v \in V\}$. Normally, the range of values for$\gamma$is (0.6, 1].

Definition 2 (Maximal$\mathbf{\gamma }$-Quasi-Cliques) [13].

For the graph$G=\left(V, E\right)$ and node-set $X \subseteq V$, if G(X) is a $\gamma$-Quasi-Cliques, and there is no more node-set $Y\supset X$ that makes G(Y) to be a $\gamma$-Quasi-Cliquess, and we call G(X) as Maximal $\gamma$-Quasi-Cliques.

Definition 3 (Formal Concept Analysis, FCA)[21].

 

Formal Context: Let$F=\left(O, A, I\right)$be a formal context, where$O=\left(O_1, O_2, \dots , O_n\right)$, is the set of objects,$A=\left(A_1, A_2, \dots , A_n\right)$is the set of attributes, and I is a binary relation between O and A.

Operators ↑ and↓:Let$F=\left(O, A, I\right)$be a formal context. The operator↑ and↓ on X⊆ O and Y⊆ A are defined as:

X↑ = {a ∈ A|∀o ∈ X,(o,a) ∈ I}

Y↓ = {o ∈ O|∀a ∈ Y,(o,a) ∈ I}

Formal Concept:For a formal context$F=\left(O, A, I\right)$, if$\left(O, A\right)$satisfies O↑ = A and A↓ = O,$\left(O, A\right)$is called a Formal Concept, and O is the extent of the concept, A is the intent of the concept. All formal concepts form the formal concept lattice by the partial relation are as (O1, A1) ≤ (O2, A2) O1⊆ O2( A1⊇ A2).

In our early work [13], we proved that according to calculating and utilizing the extent or intent of the concept in the formal concept lattice, we can obtain the node number in each $\gamma$-Quasi-Cliques, and then we can calculate the degree in each $\gamma$-Quasi-Cliques and determine whether it satisfies $de{g}^G\left(V\right)\ge \gamma \left(\left|V\right|-1\right)$ (refer to Definition 1). This process is represented by pseudocode as Algorithm 1:

Algorithm 1$\gamma$-Quasi-Cliques Detection

$1: \mathrm{Input} \gamma ,$formal context f 2: begin 3: Formal Concept Lattice ← Construct FCA(f) 4: for each concept ∈ Formal Concept Lattice: 5: value ← $\gamma$ * concept.extent.length 6: flag ← True 7: degree ← degree(all nodes of concept) 8: if value > degree: 9: flag = False 10: if flag is True: 11: QuasiCliques.add(concept) 12: return QuasiCliques 13: End

3.2. Methodology of Maximal Balanced $\gamma$-Quasi-Cliques Detection

3.2.1. Overview

In this subsection, we present the overall framework of the methodology of this paper, shown as Figure 5. The method in this paper is able to be divided into three steps: consider the mutual influence between nodes, re-compute the weights of the edges; generate positive, negative and weightless matrices, and obtain the corresponding Quasi-Cliques, namely QC(A_MP), QC(A_MN) and QC(A_MT); detect maximal balanced $\gamma$-Quasi-Cliques.

3.2.2. Optimization of Weight Matrix Computation

As the value of length $\zeta$ in Equation (4) is $\zeta \in \left[1, \infty \right)$, a large amount of calculations will still be generated when ${\beta }_{\zeta }=\frac{1}{\zeta !}$ gradually approaches 0 ($\zeta goes to infinity$); thus, a reasonable maximum length $\zeta$ is selected in this paper. As mentioned in Section 2, after referring to the six-dimensional space theory, we only focus on all paths with a path length $\zeta$ less than or equal to 6, while choosing the decaying function ${\beta }_{\zeta }=\frac{1}{\zeta !}$, we receive the weight of (u, v) equal to:

$$w_{u,v}={\displaystyle \sum }_{\zeta =1}^6[\frac{1}{\zeta !}\cdot {\left(A^{\zeta }\right)}_{u, v}=\left(I+A+\frac{A^2}{2!}+\frac{A^3}{3!}+\frac{A^4}{4!}+\frac{A^5}{5!}+\frac{A^6}{6!}\right).$$

(5)

Since most large social networks are sparse graphs [29], when performing matrix exponentiation on a large social network, we can consider a variety of existing sparse matrix exponentiation methods to improve computational efficiency, e.g., fast exponentiation for matrices [30], which leverage the paradigm to process exponentiation in parallel on GPUs [31]. At the same time, in this paper, we only focus on the first 6th power operation of the matrix instead of the high-power operation. Compared with Equation (4), the complexity of the matrix power operation in this paper is not high.

3.2.3. Our Maximal Balanced $\gamma$-Quasi-Cliques Detection Method

• Step 1 (Complete Weighted Matrix and Prune Data): Make complete weight in the social network graph by Equation (5) and convert it into an adjacency matrix. All elements in the matrix are nonzero after the N power operation of the matrix (N ≤ 6); thus, it is necessary to prune the weight closer to 0 (weight with a more neutral bias). For this, we will provide two thresholds, τ₁ and τ₂ (given by users).

• If the weight of two nodes is greater than the $\tau$₁, we regard the edge of these two nodes as a positive edge, noted as 1. If the weight of two nodes is less than $\tau$₂ ($\tau$₂ is negative), and there is a negative relationship between these two nodes, noted as −1; the remaining nodes are of no relationship and are noted 0. The new adjacency matrix AM is shown in Equation (6).

  $${\mathrm{A}}_{\mathrm{M}}=\{\begin{array}{c}1, if w\left(e \right)=w\left(v_i, v_j\right)>{\tau }_{1 }\\ -1, if w\left(e\right)=w\left(v_i, v_j\right)<{\tau }_2 \\ 0, otherwise \end{array}$$

  (6)

• Step 2 (rebuild the signed matrixes): Since the $\gamma$-Quasi-Cliques Detection method in Section 3.2.1 is assigned to unweighted and normal social networks (the edges do not have positive/negative relations), in this step, we redefine A_M as three matrices. All positive edges are stored in A_MP, all negative edges are stored in A_MN and edges with weights 1 and −1 are regarded as 1 in A_MT, which only indicates whether there is a relationship between the nodes.

  $${\mathrm{A}}_{\mathrm{MP}}=\{\begin{array}{c}1, if w\left(e \right)=w\left(v_i, v_j\right)=1\\ 0, if w\left(e\right)=w\left(v_i, v_j\right)=-1 \\ 0, otherwise \end{array}$$

  (7)

  $${\mathrm{A}}_{\mathrm{MN}}=\{\begin{array}{c}0, if w\left(e \right)=w\left(v_i, v_j\right)=1\\ 1, if w\left(e\right)=w\left(v_i, v_j\right)=-1 \\ 0, otherwise \end{array}$$

  (8)

  $${\mathrm{A}}_{\mathrm{MT}}=\{\begin{array}{c}1, if w\left(e \right)=w\left(v_i, v_j\right)=1\\ 1, if w\left(e\right)=w\left(v_i, v_j\right)=-1 \\ 0, otherwise \end{array}$$

  (9)

• Step 3 ($\gamma$-Quasi-Cliques Detection): Using these three matrixes as input values, perform Quasi-cluster detection to obtain Quasi-Cliques sets QC(A_MT), QC(A_MP), and QC(A_MN), if the Quasi-Cliques in quasi-clusters QC(A_MP) and QC(A_MN) exist in QC(A_MT), then they are our final output: Signed $\gamma$-Quasi-Cliques.

Notes: The QC(A_MP) is the set of$\mathbf{\gamma }$-Quasi-Cliques with positive edges, the QC(A_MN) is the set of$\mathbf{\gamma }$-Quasi-Cliques with negative edges, the QC(A_MT) is the set of$\mathbf{\gamma }$-Quasi-Cliques with positive edges and negative edges (regardless of the sign of the edges). If the$\mathbf{\gamma }$-Quasi-Clique E₁ and$\mathbf{\gamma }$-Quasi-Clique E₂ are both in the QC(A_MP), there are positive relationships among the nodes in E₁ and E₂, respectively, the E₁ and E₂ form a$\mathbf{\gamma }$-Quasi-Clique in QC(A_MN), and there are negative relationships among the nodes in merger set of E₁ and E₂. Meanwhile, the merger set of E₁ and E₂ with positive and negative edges is a$\mathbf{\gamma }$-Quasi-Clique in QC(A_MT), which means that all nodes in E₁ and E₂ can form a$\mathbf{\gamma }$-Quasi-Clique. At this point, this$\mathbf{\gamma }$-Quasi-Clique is a maximal balanced$\mathbf{\gamma }$-Quasi-Clique.

To explain the above notes more intuitively, here is an example to illustrate:

Figure 6a, shows a signed network graph with six nodes, including positive and negative edges between all nodes. According to Equations (7) and (8), the sub-networks corresponding to the positive and negative edges we obtained are shown in Figure 6b and Figure 6c, respectively. Figure 6d conveys all positive and negative edges to unweighted edges. The matrixes corresponding to Figure 6b,c are A_MP and A_MN, and Figure 6d corresponds to the matrix A_MT.

When $\gamma =0.6$, in Figure 6b, it is easy to find 2 0.6-Quasi-Cliques with positive edges: {1,2,4} and {3,5,6}. In Figure 6c, {1,2,3,4,5,6} is a 0.6-Quasi-Clique with negative edge., and {1,2,3,4,5,6} is a 0.6-Quasi-Clique without weight in Figure 6d. At this time, we regard {{1,2,4}, {3,5,6}} as a maximal balanced 0.6-Quasi-Clique, in which {1,2,4} and {3,5,6} are two sub-0.6-Quasi-Cliques, which are positive within these two 0.6-Quasi-Cliques, and negative between these two 0.6-Quasi-Cliques.

Algorithm 2 explains steps 1–3.

Algorithm 2 The overall flow of community detection algorithms

$1: \mathrm{Input} \gamma ,$graph g, thresholdτ1, τ2 2: begin 3://Complete Weighted Matrix and Prune Data 4: Formal Concept f ← Calculate g by Equation (5) and compare it with threshold τ1, τ2. 5://Rebuild the signed matrixes 6: AMP, AMN, AMT ← Matrix Equation (7) (AM), Matrix Equation (8) (AM), Matrix Equation (9) (AM) 7://Detecting $\gamma$-QuasiCliques 8: $\gamma$-QuasiCliques1, 2, 3 ← Algorithm 1 ($\gamma ,$ AMP), Algorithm 1 ($\gamma ,$ AMN), Algorithm 1 ($\gamma ,$ AMT) 9: for Q1 in $\gamma -$ QuasiCliques1: 10: for Q2 in $\gamma -$ QuasiCliques2: 11: if Q1 and Q2 in $\gamma -$ QuasiCliques3: 12: $\mathrm{Signed} \gamma$-Quasi-Cliques ← (Q1, Q2) 13: return Signed $\gamma$-QuasiCliques 14: End

4. Experiment and Discussion

4.1. Recompute Weight Matrix and Threshold Determination

4.1.1. Dataset and Experimental Environment

The dataset we use in this section comes from the SNAP public dataset (https://snap.stanford.edu/data/, accessed on 10 July 2009). We apply the “Bitcoin Alpha trust weighted signed network” dataset [32,33] in our experiment. In this dataset, there are 3783 nodes and 24,186 edges, and the weights of edges are on a scale of −10 to +10. The weights are the rating of trust, and members of Bitcoin Alpha rated other members on a scale from −10 (total distrust) to +10 (total trust) in the steps of 1, representing the reputation of users (nodes).

To make the visualization of the clustering results in Section 4.1.2 clearer, we only extracted the first thousand nodes in this dataset to execute our model. Figure 7 is a network graph composed of one thousand nodes.

All experiments in this section run on Windows 10 operating system, Intel Core i7 CPU, 2.90 GHz, and 32 GB RAM.

4.1.2. Threshold Determination

1

The value determination of $\tau$

In order to obtain more evident weight edges for positive/negative attitudes of users, we calculated the mean and standard deviation of the matrices A_MP and A_MN, and pruned the data by giving different threshold ranges of $\tau$₁ and $\tau$₂ according to the statistical 68–95–99.7 rule. The four subgraphs in Figure 8 are the distribution of node degrees after setting $\tau$₁ and $\tau$₂ in

Table 1. Different values of $\tau$₁ and $\tau$₂.

	Subgraph (a)	Subgraph (b)	Subgraph (c)	Subgraph (d)
$\tau$1	Mean(AMP)	Mean(AMP) + Std(AMP)	Mean(AMP) + 2 × Std(AMP)	Mean(AMP) + 3 × Std(AMP)
	11,377.463	66,294.718	119,731.322	173,936.850
$\tau$2	Mean(AMN)	Mean(AMN) − Std(AMN)	Mean(AMN) − 2 × Std(AMN)	Mean(AMN) − 3 × Std(AMN)
	−1074.750	−18,230.686	−35,300.547	−52,414.579

. It is easily observable that when the values of $\tau$₁ and $\tau$₂ are equal to the values in subgraph (d), the pruned data better preserve the structure of the original data.

In addition to comparing the node degree centrality of the four thresholds, we also compare the number of edge prunings under different thresholds.

In order to make the recomputed weight matrix closer to the sparse matrix of the real social network, we prefer to prune edges through a threshold, so as to obtain those edges with more extreme weights. In

Table 2. The number of edges with different values of $\tau$₁ and $\tau$₂.

	Subgraph 8(a)	Subgraph 8(b)	Subgraph 8(c)	Subgraph 8(d)
Number of Prune Edges	707,589	858,691	879,438	887,651
Number of edges	292,411	141,309	120,562	112,349

, we can see that subgraph (d) has the most pruned edges, excluding redundant data.

2

The value determination of γ

We input the dataset of Figure 8d in the previous subsection as the pruned dataset into our model for the$\gamma$-Quasi-Cliques detection.

Table 3. The number of Quasi-Cliques and nodes coverage with different values of $\gamma$.

	$\mathit{\gamma }=0.6$	$\mathit{\gamma }=0.7$	$\mathit{\gamma }=0.8$	$\mathit{\gamma }=0.9$	$\mathit{\gamma }=1$
Number of Quasi-Cliques	170	127	67	32	8
$\mathrm{Number} \mathrm{of} \mathrm{Nodes}$	168	146	107	65	43

shows the number of Quasi-Cliques and node coverage detected with different values of $\gamma$.

It is known from Table 3 that some nodes overlap in different $\gamma$-Quasi-Cliques, and the higher the degree of overlap of these nodes, the more important they are in the network.

In order to observe the $\gamma$-Quasi-Cliques density with different $\gamma$ values more intuitively, we provide a Quasi-Clique node density formula to evaluate the quality of the threshold.

Definition 4.

(Quasi-Clique Node Density, QND)

$$QND=\frac{The total number of nodes in \gamma -Quasi-Cliques}{The number of nodes in the network} (\gamma =0.5, 0.6, 0.7, \dots , 1)$$

Table 4. The number of QND with different values of $\gamma$.

	$\mathit{\gamma }=0.6$	$\mathit{\gamma }=0.7$	$\mathit{\gamma }=0.8$	$\mathit{\gamma }=0.9$	$\mathit{\gamma }=1$
QND	0.168	0.127	0.107	0.065	0.043

shows the results of QND.

From Table 4, we find that when the value of $\gamma$ is smaller, the number of detected nodes is larger, the coverage rate in the network is larger, and more maximal balanced $\gamma$-Quasi-clques can be obtained.

Figure 9a–e represents the nodes distribution of detected $\gamma$-Quasi-Cliques in all cases of $\gamma$ = 0.6~1, respectively. In each subgraph, the nodes in the same Quasi-Cliques are represented by the same color. The black nodes are single nodes, which do not belong to any Quasi-Cliques. According to the data in Table 2 and the density of the subgraphs in Figure 5, we can easily find that the density of subgraphs decreases as the value of $\gamma$ increases. When $\gamma =0.6$, we obtain the densest clustering result.

4.2. Case Study

In this subsection, we present a case study to illustrate our method by real-life signed social network data. Figure 10 is a real-world signed network showing a relational network of 10 parties of the Slovene Parliament in 1994 [34]. Here are the signed social network and the matrix.

By completing the weight matrix and running it in our model, we obtain Quasi-Cliques of different sizes according to different $\gamma$ values.

Figure 11 shows the sub-network corresponding to the matrix A_MP that retains all positive edges (since a detailed example has been given in the previous section, here, only the positive sub-network is used as an example to illustrate).

When $\gamma =0.6$, there are two 0.6-Quasi-Cliques in QC(A_MP), which are: {1,3,6,8,9}, {2,4,5,7,10}. For the nodes set {1,3,6,8,9}, γ(|V| − 1) = 0.6 × (5 − 1) = 2.4, and the degree of all nodes is 4; they are larger than 2.4, and they are suitable to the condition degG (V) ≥ γ(|V| − 1).

Similarly, we find one Quasi-Cliques in QC(A_MN), which is: {1,3,6,8,9,2,4,5,7,10}. Meanwhile, there is one 0.6-Quasi-Cliques in QC(A_MT): {1,3,6,8,9,2,4,5,7,10}. Thus, we can obtain the maximal balanced 0.6-Quasi-Cliques: {{1,3,6,8,9},{2,4,5,7,10}}.

Figure 12 shows the results. The same color of nodes is the same Quasi-Cliques.

Since nodes in a social network correspond to individuals, “places that individuals like to visit” can be regarded as attributes of nodes. Through text mining and other technologies, we are able to mine large social networks with place attributes from social networks such as Twitter, Facebook, and Weibo. Therefore, in real life, different communities have different types of third places to gather, such as cafes, parks, or religious churches. In practical application, we can provide reasonable references for the layout and planning of public places according to the different places mapped to the detected community.

To facilitate understanding the idea of this paper, we simulate that the nodes in the dataset in this case frequently visit some “third places”. Node attributes are as follows in

Table 5. Simulate attributes of nodes.

Node	Frequently Visited Third Place
1	Coffee, Church
2	Bar, Coffee, Community Center
3	Church, Park, Coffee
4	Park, Bar, Coffee, Community Center
5	Community Center, Coffee
6	Park, Church
7	Bar, Community Center, Coffee
8	Church, Coffee, Bar
9	Mall, Church
10	Park, Community Center, Coffee

:

From the above analysis, the social network contains two communities: C1: {1,3,6,8,9} and C2: {2,4,5,7,10}. According to the different attributes of the nodes simulated in Table 5, it is not difficult to find that the nodes in C1 often visit churches, while the nodes in C2 prefer to visit cafes and community centers.

5. Conclusions

Communities in social networks often gather in some urban public places. In order to make reasonable suggestions for urban land division, it is a meaningful topic to study how to effectively detect communities in signed social networks. This paper focuses on mining the maximal balanced $\gamma$-Quasi-Cliques in signed networks for detecting communities. We proposed a model to solve the problems in three steps: First, we recomputed the weights of edges based on the mutual influence of common friends, and we defined and determined some threshold ($mean\pm n\ast std$), (n = 0, 1, 2 and 3) for our pruning data process. Second, we proposed three new definitions of matrixes A_MP, A_MN and A_MT to calculate the $\gamma$-Quasi-Cliques with positive, negative or unweighted edges by FCA method, respectively. Third, We filtered and detected the maximal balanced $\gamma$-Quasi-Cliques. In the experiment, we applied the real-life data to our model, and compared results with different $\gamma .$ Additionally, to help readers understand the proposed model on an intuitive level, we provided a case study. Experiments proved its effectiveness. In the future, we will consider improving the efficiency of our algorithm for the dynamic signed social network.