An Empirical Study of Absolute-Fairness Maximal Balanced Cliques Detection Based on Signed Attribute Social Networks: Considering Fairness and Balance

1. Introduction

People in the real world assume multiple characteristic labels, such as gender, job, nationality, location, education, and profession, and the above information can be formed as a complex network. A complex network is formed based on the combination of information on interpersonal relationship and personal labels into a social network graph. Indeed, social networks are generally represented as a graph consisting of nodes and edges. Especially, each node in a real-life social network can be regarded as an individual or an organization, and an edge can be expressed as a relationship between each individual or organization. Normally, a social network, which is formed as a graph, can effectively explain the social relationships between individuals or organizations and their respective characteristics.

Community detection in the study of complex networks is an area of graph analysis that has recently garnered keen attention and entails discovering cohesive subgraphs in the network. A cohesive subgraph is often used to identify the dense community structure of social networks, with cliques utilized as a common method for this purpose [1].

Clique mining is a commonly used technique in graph analysis and has applications in detecting protein structures and enumerating clusters [2]. It is also useful for detecting social network structures, such as identifying overlapping communities. Mining cliques have various applications and improved methods in graph analysis and other fields [3,4], specified as follows:

· Protein structure detection: Cliques can be used to identify substructures in protein interaction networks, which can help in understanding protein function and disease mechanisms.

· Cluster analysis: Cliques can be used to identify densely connected clusters in a graph, which can help in understanding a graph’s structure and the relationships between its components.

· Recommendation systems: Cliques can be used to identify groups of users with similar interests or preferences, which can be used to make personalized recommendations.

Social network graphs can be categorized based on the types of edges, whether it is weighted or unweighted. A social network is called a signed social network when it has positive or negative weighted edges. Several studies have been conducted to analyze signed social networks, with specific emphasis on examining the balance of the network or its subnetworks. The theory of social balanced networks is often used to define the concept of "balance" in signed social networks.

It is interpreted using the phrases “the friend of my friends is my friend,” “the enemy of my friends is my enemy,” “the friend of my enemies is my enemy,” and “the enemy of my enemies is my friend” [5]. The “social balanced theory” can be illustrated in Fig. 1.

Fig. 1 illustrates the cases of “social balance theory,” whereby on the edges, the sign “+” denotes “friend”/ “positive” and “-” denotes “enemy”/ “negative,” The first two triangles are balanced and the last two are unbalanced.

A node in an attribute network can contain a large amount of attribute information. Studies [6,7] explored mining communities in attribute networks, aiming to detect communities that satisfy specific attribute constraints or exhibit high correlations among attributes. However, these studies often do not consider the attributes of nodes by the concept of “fairness” within the community. Usually, the concept of “fairness” has gained more attention in AI as a means of improving the reliability of machine learning [8,9]. Recently, new research has emerged that combines the detection of cliques in attribute graphs with the consideration of fairness [10,11].

Unlike existing works, this study is devoted to providing an enumeration method to detect the maximal balanced cliques by considering both the “fairness” and “balance” in social networks. In this context, the fairness of each clique is absolutely fair.

Since the detection of the balance cliques can mitigate problems such as the existing “information cocoon” [12], if we consider fairness at the same time, by constraining some attributes of the nodes in cliques, we can only get the maximal cliques formed by some nodes that we are interested in. Hence, the maximal cliques have the two characteristics of “fairness” and “balance.” For instance, in a real-life social network, where each individual has an attribute representing one’s gender, if we focus on mining a community with an equal number of men and women, gender bias can be overcome by detecting the attribute community [11]. As an alternative approach, our objective is to identify communities of researchers from various fields in a collaborative network, with each node being associated with an attribute that denotes their research topic. The fairness cliques can consider the fairness of various research topics. With this in mind, combining the maximal balanced cliques with absolute fair cliques in a signed attributed social network can produce very meaningful results.

The following describes the structure of the paper. The first section presents the introduction, which includes the literature survey done and the related work researched on maximal balanced cliques and fairness cliques. In the second section, several related works about community mining in attributed social networks and signed social networks, and the fairness-oriented research are summarized. In the third section, the preliminary knowledge of social network analysis, maximal balanced cliques and fairness in attributed social networks used for organizing our research are presented in that order. In the fourth section, we illustrate the problem statement and propose a methodology and an algorithm. The algorithm detects maximal balanced cliques and determines whether the cliques are fair, and if it is not fair, we shall determine whether sub-cliques can be derived to ensure fairness. In the fifth section, we elaborate on the introduction of datasets of a research company and execute an empirical study to get the absolute fair maximal balanced cliques for the above company. Finally, in the last section, our work in this paper is brought to a conclusion and further works of the paper are discussed.

The principal contributions of this paper are specified as follows:

· Novel model: A novel model for detecting absolute-fairness maximal balanced cliques is proposed in this paper. We first propose a novel definition called absolute-fairness maximal balanced cliques.

· Advanced algorithm: We propose a novel algorithm to detect absolute-fairness maximal balanced cliques by the modified three-way concept lattice method and fairness method.

· Empirical study: To illustrate how the model works, we have conducted a case study based on the real-life datasets in the experiment section.

2. Related Works

2.1 Community Mining in Attribute Social Network & Signed Social Network

Several types of research aimed to mine the attributed graph in attributed social networks for the existing social network analysis and graph mining studies. The problem of community detection in attributed social networks (attribute graph) is a hot topic in community mining. Fang et al. [13] proposed an attributed community search method and introduced CL-tree, an index structure. Khan et al. [14] involved the work regarding mining subgraphs whereby the nodes in the subgraph are closely connected, and each node satisfies the attributes (keywords) queried. Li et al. [15] focused on detecting the attributed communities in the attributed graph based on an embedding model. Pizzuti and Socievole [16] detected the attribute communities by considering both node similarity and structural connectivity in attributed social networks.

At present, there are also many related works on the analysis and mining of signed social networks. Chen et al. [17] proposed a method to enumerate the maximal balanced clique in signed networks. Salminen et al. [18] developed an online hate classifier to analyze the signed social networks. Moreover, [19] denotes our previous work about detecting maximal balanced cliques by three-way concept lattice. In this work, we have proposed two algorithms called MCDA1 and MCDA2 to mine the maximal balanced cliques.

2.2 Fairness-Aware Mining

There are also some studies about the concept of “fairness” in attributed social network analysis. Pan et al. [11] proposed a SFCEnum method to enumerate the strong fair cliques in attribute graphs, and they first introduced the concept of “fairness” for cohesive subgraphs. Beutel et al. [20] introduced “fairness” into the recommendation system and displayed metrics to evaluate the algorithm's fairness. Hao et al. [10] first combines the formal concept analysis (FCA) with fairness-aware data mining in attributed social networks to mine the absolute-fairness cliques. In this work, they proposed the new concept of “absolutefairness” to give strict constraints to ensure that the number of nodes for each attribute is the same in each clique.

Compared to the existing studies, our work has considered both “fairness” and “balanced” in signed attributed social networks as different from the literature on social network analysis and community detection.

3. Basic Knowledge

This section presents our developed MCDA method [19] based on three-way concepts for detecting maximal balanced cliques.

The term “signed attributed social network” is defined as G = (V, E, W) in [13]. Here, V refers to a collection of nodes, [TeX:] $$\mathrm{V}=\left\{\mathrm{v}_1, \mathrm{v}_2, \mathrm{v}_3, \ldots, \mathrm{v}_{\mathrm{n}}\right\}$$, while E indicates the edges present in the network, [TeX:] $$E=\left\{e_{i j} \mid\right.\mathrm{i}, \mathrm{j} \in \mathrm{V}\},$$ which includes all possible edges. Additionally, W denotes the set of weights associated with the edges, where “+” and “-” are used in this study to represent positive and negative weights, respectively. Therefore, [TeX:] $$\mathrm{W}=\left\{\mathrm{W}^{+} \cup \mathrm{W}^{-}\right\}.$$ As shown in Fig. 2, among them, the positive edges are represented by solid lines, and the negative edges are denoted as dashed lines.

Definition 1 (Modified formal context & adjacency matrix) [19]. For a signed network G = (V, E, W), we use modified formal context [TeX:] $$\mathrm{F}=\left(\mathrm{V}, \mathrm{V}, \mathrm{W}^{+}\right)$$ and modified supplement formal context [TeX:] $$\mathrm{Fc}=\left(\mathrm{V}, \mathrm{V}, \mathrm{W}^{-}\right)$$ to represent the positive/negative relationship between nodes, respectively. Based on F and [TeX:] $$\mathrm{F}^{\mathrm{c}},$$ there are two adjacency matrixes that have been obtained by formulas (1) and (2), and these matrixes contain only 0 and 1. The matrixes of Fig. 2 above are shown in Tables 1 and 2.

Based on the traditional formal concept lattice method [21], when Tables 1 and 2 are used as the input, after all rows and columns are intersected respectively, we can get two concept lattices, as shown in Fig. 3. Each node in the lattice is a concept node, with the blue text denoting the extent of the concept, and the red text denoting the concept's intent.

In our previous work [19], we proposed and proved a method to get the three-way concept lattice based on the above FCA method. The steps are to intersect the extent of the concepts in the two concept lattices in Fig.3 above in pairs, and combine the intent in pairs to obtain a new concept: OE concept (e.g., ({1, 2, 3, 4}, {1, 2, 3, 4}) and ({1, 2, 3, 4}, {5, 6, 7, 8, 9}) → ({1, 2, 3, 4}, ({1, 2, 3, 4}, {5, 6, 7, 8, 9}))), such that all OE concepts can form an OE concept lattice through a certain partial order structure, as shown in Fig. 4.

For each OE concept, we can think of a pair of node sets as a maximal balanced clique, if the first half of the pair is equal to the left subset of the second half (e.g., for the OE concept ({1, 2, 3, 4}, ({1, 2, 3, 4}, {5, 6, 7, 8, 9})), the first half (1, 2, 3, 4) and the left subsets of the second-half part ((1, 2, 3, 4), (5, 6, 7, 8, 9)) are equal), shows as Fig. 5. Therefore, the node set contained in this OE concept is a maximal balanced clique node set. In this context, there are all positive edges inside the two subsets and all negative edges between the two subsets.

4. Problem Statement & Proposed Approach

Here, we will illustrate the problem statement and explain the proposed approach to detect absolute fair maximal balanced cliques in the signed attributed social network.

We have introduced some definitions in our previous work in [22], and this paper is the extension of the conference paper. Based on the content of [22], we have given a complete process for detecting maximal balanced cliques and absolute-fairness cliques in Sections 3 and 4. Meanwhile, we intend to apply this model to a real-life dataset and give an empirical study in Section 5.

4.1 Problem Statement

To enhance comprehension, we present some definitions as follows.

At first, we have defined signed attributed social networks and absolute fair maximal cliques [10].

In comparison to a signed social network, a signed attributed social network includes attribute information of the nodes. It can be represented as G = (V, E, W, A), where V denotes the set of nodes, E denotes the edges present in the network, W indicates the weight set of edges, where “+” and “–” are used to denote a positive and negative weight, respectively, [TeX:] $$\mathrm{W}=\left\{\mathrm{W}^{+} \cup \mathrm{W}^{-}\right\},$$ and A denotes the set of attributes on the nodes.

Definition 2 (Criteria of fairness and maximal of absolute fair maximal clique). A clique in graph G = (V, E, A) is considered an absolute fair maximal clique if it meets the following criteria as specified:

– Fairness: It is fair, meaning the number of nodes associated with each attribute [TeX:] $$a i \in A$$ is equal.

– Maximal: It is maximal, meaning no clique [TeX:] $$\mathrm{C}^{\prime}$$ is a proper superset of C and also meets the fairness condition [22].

Fig. 6 shows a social network graph with nodes, edges, and the attributes of nodes (‘a’ and ‘b’ represent the attributes of nodes, such as node V1 belonging to Class ‘a’ and node V8 belonging to Class ‘b’). The clique in Fig. 6 is a fairness clique since the numbers of the attribute of nodes are the same (e.g., the number of attributes ‘a’ and ‘b’ are both equal to 4).

Then, to enhance comprehension, we have defined the maximal balanced clique (MBC) and absolute fairness maximal balanced clique (AFMBC) [22].

Definition 3 (Maximal balanced clique). A fully connected subgraph [TeX:] $$\mathrm{G}_1$$ of a signed network (which is described as G = (V, E, W)) is called a maximal clique. Moreover, if [TeX:] $$\mathrm{G}_1$$ is a maximal clique and for [TeX:] $$\forall(u, v) \in \mathrm {MBC},\mathrm{(u, v)} \in \mathrm{W}\left(\mathrm{W}=\left\{\mathrm{W}^{+} \cup \mathrm{W}^{-}\right\}\right),$$ is a MBC. To further refine the definition, an MBC can be divided into two sub-cliques [TeX:] $$\mathrm{C}_1 \text{ and } \mathrm{C}.$$ To ensure “balance”, a new requirement has been proposed such that for [TeX:] $$\forall \mathrm{u}, \mathrm{v} \in \mathrm{C}_1 $$ or [TeX:] $$\mathrm{u}, \mathrm{v} \in \mathrm{C}_2,(\mathrm{u}, \mathrm{v}) \in \mathrm{W}^{+} \text {, }$$ and when [TeX:] $$\forall \mathrm{u} \in \mathrm{C}_1, \mathrm{v} \in \mathrm{C}_2$$ or [TeX:] $$\mathrm{u} \in \mathrm{C}_2, \mathrm{v} \in \mathrm{C}_1$$ the u and v have negative edges, which are indicated as [TeX:] $$(\mathrm{u, v}) \in \mathrm{W}^{-}$$.

Definition 4 (Absolute fairness maximal balanced clique). An AFMBC can be defined as a pair of subcliques [TeX:] $$\mathrm{C}_1 \text{ and } \mathrm{C}_2$$ that satisfy both “fairness” and “balance,” so that the union of the two cliques, [TeX:] $$\mathrm{C} = \mathrm{C}_1 \cup \mathrm{C}_2,$$ is an AFMBC.

Definition 5 (Derived pseudo absolute-fairness maximal balanced clique). For the maximal balanced cliques in which the numbers of attributes are greater than the kinds of attributes and the numbers are unequal, we will derive the sub-absolute fairness maximal balanced clique (sub-AFMBC) as the outcomes.

Example: To illustrate, consider {(1,2,3,4), (5,6,7,8,9)} in Fig. 7 is an AFMBC. However, (5,6,7,8,9) is a clique, but it violates the fairness constraint such that we remove this clique and generate several new pseudo-AFMBC: (6, 7, 8, 9), (5,7,8,9), and (5,6,7,8). Finally, we obtain three AFMBCs that satisfy both fairness and balance: {(1,2,3,4), (6,7,8,9)}, {(1,2,3,4), (5,7,8,9)}, and {(1,2,3,4), (5,6,7,8)}. This process is demonstrated in Fig. 7.

Problem statement: Given a signed attributed social network G, by finding all AFMBCs in G, the cliques set Ω containing the AFMBCs is expressed as follows:

4.2 Methodology

This section introduces the method for identifying AFMBC in signed attributed social networks.

In previous research [19], we demonstrated the equivalence between MBCs and the OE-concept in the OE-concept lattice using the three-way concept method. We used modified formal contexts, which include positive and negative formal contexts as subgraphs, to mine MBCs.

Our work has taken into account not only the “balanced” aspect but also “fairness.” Therefore, in addition to using the three-way concept method to obtain the MBCs, we have also analyzed the attributes of the nodes and ensured that the number of each attribute in each sub-clique of MBCs is equal.

The following are the technical steps of our method as specified:

Step 1: For a given G = (V, E, W, A), based on Definition 1, two adjacency matrixes of modified formal context F and [TeX:] $$\mathrm{F}^\mathrm{C}$$ are obtained.

Step 2: The MCDA method is applied to detect the MBCs by generating the corresponding OE-concept lattice.

Step 3: Travel all MBC and determine the fairness with each sub-clique of a pair, and filter the AFMBC that satisfies Definition 4, otherwise, derive the pseudo-AFMBC (based on Definition 5) from an MBC to make sure the number of attributes is equal.

Fig. 8 illustrates the framework of our methodology, which includes all the above steps.

The method is explained in pseudocode and presented as follows.

5. Experiment

5.1 Dataset Setting

For implementing the proposed algorithm, we used a real-life signed attributed social network: namely, a research team at a manufacturing company [23] (https://toreopsahl.com/datasets/#FreemansEIES). We used Python 3.8 and Intel Core i5 processors on MacOS to execute the experiment.

Intra-organizational networks contain two company members’ social networks. In our work, we have utilized one of the networks of 77 researchers. The network concerned constitutes 77 researchers and their opinions as to one another's knowledge and abilities. The scores range from 0–6 and are used to represent weight levels in the network. A score of 0 indicates no knowledge of the person, while scores of 1 and 2 indicate strong disagreement and disagreement, respectively. Then, scores of 3 and 4 indicate neutrality, whereas scores of 5 and 6 indicate agreement and strong agreement, respectively. To preprocess the data, scores of 1 and 2 are treated as extremely negative ratings and labeled as -1, whereas scores of 5 and 6 are treated as extremely positive ratings and labeled as 1. Scores that fall between these extremes are labeled as 0.

The information on researchers include location, tenure, and organizational level. In our work, we have chosen the tenure (short-tenured, less than 61 months; long-tenured, greater than or equal to 61 months) and the organization level (management: global department manager, local department manager, and project leader; general: researcher) as the attributes to analyze this network.

5.2 Empirical Study

The concept of “group polarization” was initially introduced by Stoner in 1961 in the field of sociology. Later on, Sunstein [24] defined “group polarization” as a phenomenon where group members tend to hold certain opinions or attitudes at the beginning, and after deliberation, they continue to move in the direction of their initial biases, eventually leading to the formation of an extreme point of view.

In fact, company managers prefer employees to reduce group polarization as much as possible in the work process. Therefore, managers may need to make necessary interventions on social networks. However, if the intervention method is only a single-shielded communication due to the internal structure of the social network, it is not conducive to crossing the conceptual gap. Therefore, maintaining an openness to multiple concepts and allowing isolated “small worlds” in social networks to perceive each other are a meaningful way to finally de-polarize them [25]. This empirical study seeks to find as many small groups as possible with polarized tendencies (i.e., MBCs). The goal is mainly based on the professionalism ratings of 77 employees of the research company and aims to ensure that positions or work experience in the cliques have “fairness” (i.e., absolute-fairness balanced cliques) and to enumerate all possible cooperative groups, establishing opportunities for cooperation and communication between isolated “small worlds,” so that polarization is reduced within the company's employees.

Fig. 9 illustrates the signed attributed social network of this dataset. Each node represents one employee, and the solid lines (gray) and dashed lines (blue) represent the positive and negative relationship between employees, respectively.

Taking this dataset as input, after calculating with our method, we get two MBCs: ({28, 63, 73, 74, 76}, {15, 49}), ({10, 55, 68}, {1, 2}). This means that these two MBCs are possible to have group polarization. To address this issue, we have considered the “fairness” of the cliques by considering working hours (tenure) and work positions (organization level) as attributes, respectively. Then, we propose some grouping suggestions for cooperative groups to reduce the problem of group polarization by letting employees on the list work cooperatively with a possibility of occurrence.

These MBCs with two attribute labels are shown in Figs. 10 and 11. These figures represent two subgraphs of the network graph shown in Fig. 9. Similarly, each node represents one employee, while solid lines (gray) and dashed lines (blue) represent the positive and negative relationship between employees, respectively.

Table 3 shows the number of cliques in different situations. It includes the number of cliques detected by sub-networks that contain only positive edges, networks that contain only negative edges, and unsigned networks (which do not distinguish between positive and negative, with both weights -1 and 1 being regarded as 1). At the same time, we also derive one of the goals of our paper—MBCs in signed social networks.

According to Table 3, it is obvious that there are many cliques in this social network, whether they are positive, negative, or regardless of trust. However, only two maximal cliques are balanced (shown in the last column in Table 3), and they also account for two of the groups where group polarization is possible. The goal of the algorithm in this paper is to find these specific cliques and analyze them. Table 4 provides a detailed analysis of these two maximal balanced cliques and derives the sub-cliques from them.

Table 4 denotes the outputs of the empirical study. All the absolute-fairness maximal cliques are enumerated in this table. Company managers can group cooperative groups according to this strategy, with the result of eliminating the problem of group polarization between these two MBCs. At the same time, it also fully considers the fairness aspect of employees' different job positions and work experiences, which in turn is more conducive to teamwork

6. Conclusion

In this paper, we have presented a method of enumerating AFMBCs, applied it to signed attributed social networks, and conducted an empirical study on real-life datasets. Firstly, we have applied the threeway concept method and list to obtain all MBCs. Then, we have filtered and derived sub-cliques conforming to fairness to guarantee the “fairness” of the detected MBC. Through our empirical study, we have demonstrated the legitimacy and meaning of our method.

In the future, we intend to emphasize more efficient methods to adapt to real-life scenarios, especially in terms of applying them to dynamic social networks and other issues.