Fuzzy Measures: A solution to deal with community detection problems for networks with additional information

Abstract

In this work we introduce the notion of the weighted graph associated with a fuzzy measure. Having a finite set of elements between which there exists an affinity fuzzy relation, we propose the definition of a group based on that affinity fuzzy relation between the individuals. Then, we propose an algorithm based on the Louvain’s method to deal with community detection problems with additional information independent of the graph. We also provide a particular method to solve community detection problems over extended fuzzy graphs. Finally, we test the performance of our proposal by means of some detailed computational tests calculated in several benchmark models.

Keywords

Fuzzy clustering networks community detection fuzzy graph

1 Introduction

Clustering methods are unsupervised learning tasks, whose main aim is the decomposition of a given input set of objects into subgroups called clusters or communities. This decomposition is based on the similarity among several objects. The goal is to obtain a partition in such a way that those objects belonging to the same community are as similar as possible, whereas that elements belonging to different clusters are as dissimilar as possible. This process of grouping elements is known as clustering.

From an extensive literature review, we have found a broad range of sectors and backgrounds in which clustering has become a widely accepted tool of exploratory data analysis and model development due to its skill to gain an interesting insight into data structure. Some of these areas are business and economics, engineering and astronomy, medical and biological disciplines [32 , 47]. In [5] it can be found a detailed motivation for this structure searching. This type of analysis has also taken an essential role in solving pattern recognition or image processing problems [49, 54]. Some examples of real-world networks whose nodes are prone to exhibit a modular structure can be found in [9, 11]. It is well established that nodes belonging to the same clusters are more likely to be ‘related’ to one another than they are to the rest of the network (Friedkin held that ‘the more distant two vertices, the less they influence each other’ [14]). The modular structure of the graphs shows clearly the relations among the, besides the inner information of the network. Then, we can affirm that one of the most important analysis to be done with reality networks is about community detection. Along the years, many authors have focused their attention on this problem. Some extensive analyses and comparison between several representative methods on community detection can be found in [25, 53]. These papers provide a clear vision of the state of art of this field.

A graph is a mathematical object that allows to model (and also visualize) the relationships that exist between a set of objects, V. In the topic of community detection problems, thousands of works can be found in which a graph models the relationships between different objects with the aim of identifying strongly cohesive communities or groups [10 , 39]. Undoubtedly, the relationships between objects (valued or not) should be the main factor when identifying communities in a network. Nevertheless, it would not be unreasonable to use additional information to which a graph provides in order to extend the concept of group or community [22, 43].

Let us illustrate this idea with a toy example. We consider a set of 10 individuals whose relationships can be seen in Fig. 1. The set of links is E = {(1, 2) , (1, 3) , (2, 3) , (2, 4) , (3, 5) , (4, 5) , (5, 6) , (6, 7) , (6, 8) , (7, 9) , (8, 9) , (8, 10) , (9, 10)}. Then, we assume that we have additional information about these 10 individuals. For example, we know their particular opinion (positive or negative) in favor of a politician. In particular, let us assume that the following vector represents the opinion of these 10 individuals O = (+ , + , + , - , - , + , + , - , - , -). From a structural point of view (i.e. the graph), any community detection algorithm will identify clearly two groups or communities: C₁ = {1, 2, 3, 4, 5} and C₂ = {6, 7, 8, 9, 10}. However, if we reformulate the idea of a group and we incorporate the information provided by each individual’s opinion, it seems logical to think that there should be four groups, C₁ = {1, 2, 3}, C₂ = {4, 5}, C₃ = {6, 7}, C₄ = {8, 9, 10}.

Fig. 1

Graph with 10 nodes.

In the literature of Social Network Analysis, (SNA), we have found some authors that have incorporated additional information to the graph to enrich some of the classic problems of this field (see for example [3 , 43]). In the case presented in [16], the information provided by a game is incorporated in order to reformulate the idea of centrality to obtain new and different measures. In the topic of fuzzy sets, we can found that the information provided by a fuzzy set has also been incorporated into the graph to enrich the classic problem of community detection or other SNA problems (see for example [12 , 48]). Nevertheless, as it is mentioned in [20], the usual way of defining fuzzy graphs only takes into account the associated uncertainty for each pair of adjacent nodes of a given graph. However, there are some situations in which this model looks insufficient to capture possible larger interactions as well as the capacity of those sets of nodes whose cardinality is greater than two.

Considering this, in this work we analyze the community detection problem when the available information has two different and independent parts: a graph G = (V, E), and a fuzzy measure μ defined over V (see [46] for further details), the set of nodes of the network. See that a fuzzy measure can be viewed as an extension of probabilistic, plausibility/belief or possibilities measures. Particularly in this paper, fuzzy measures are assumed to be the representation of the affinity among nodes. Let us remark that in this study we work in a much more general case than fuzzy graphs are, in which the only available information is about the edges of the graph: our research is based on extended fuzzy graphs, $\tilde{G} = (V, E, μ)$ . This concept was introduced in [20], where μ is supposed to define a relation among all the pairs of nodes in V.

Our starting point is one of the most popular community discovery algorithms, which was introduced in 2008 by Blondel et al. [4], called Louvain algorithm. It is based on modularity optimization, which is an NP-hard problem. In this paper, we first propose a modification of it which can manage several information sources when solving community detection problems, apart from the structure of the graph. Then, we explain a particular application of our proposal to deal with community detection problems over extended fuzzy graphs in which the fuzzy measure μ defines some affinity relation among the nodes. We also explain the particular case in which the fuzzy measure is additive so the application of our algorithm is almost trivial. To carry on with it, we first introduce the notion of the weighted graph associated with a fuzzy measure, and we propose a definition of a group based on affinity fuzzy relations.

The remainder of the paper is organized as follows. In Section 2 we introduce some new concepts related to fuzzy measures. Then, in Section 3 we work with fuzzy measures obtained from fuzzy relations. In Section 4 we propose a modification of the Louvain algorithm which can manage different information sources. We also provide a community detection algorithm to find communities in extended fuzzy graphs. The performance of our algorithm is tested with some computational results based on benchmarking in Section 5. We conclude the paper with some conclusions in Section 6.

2 Graphs, fuzzy graphs and extended fuzzy graphs

Let V = {1, …, n} be a finite set of elements called nodes, and let E = {{i, j} | i, j ∈ V} be a set of links or edges, it is, the set of neighboring or related elements of V. It is assumed that if the elements i, j are related, then ∃ e = {i, j} ∈ E; otherwise, ∄ e = {i, j} ∈ E. Hence, the pair G = (V, E) is a graph or network. A network can also be represented by means of its adjacency matrix, denoted as A. It shows the direct connections between the elements of V in that sense: if A_ij ¬ =0, then ∃ e = {i, j} ∈ E; else, if A_ij = 0, then ∄ e = {i, j} ∈ E. A particular case of graph is that in which each edge of E has a numerical weight assigned. This type of graphs are known as weighted graphs. In theses cases, ∀i, j ∈ V, the element A_ij represents the weight of the edge e = {i, j} (let us note that it has to be not negative, but not necessarily 0 or 1).

A wider concept is showed by fuzzy graphs. This type of model representation is really useful in those cases in which there exists some uncertainty or vagueness about the description of the objects, its relations, or even, in both aspects. This notion was introduced by Rosenfeld [41], and it is based on the fuzzy relations between the elements [52], under the assumption that they represent the degree of relationship between the individuals. In Definition 2 we provide a formal characterization of fuzzy graphs.

Definition 1. Fuzzy graph [41]. Let V be a nonempty set. Let be the functions η : V ⟶ [0, 1] and ψ : V × V ⟶ [0, 1] such that for all x, y ∈ V, ψ (x, y) ≤ B (η (x) , η (y)), being B a conjunction operator. Then, the triplet G = (V, η, ψ) is said to be a fuzzy graph. We call η the fuzzy vertex set, and ψ the fuzzy edge set of G, respectively.

Let us emphasize that many authors simplify previous definition of fuzzy graphs under the assumption that the fuzzy vertex is crisp, so the only information is given by the pair G = (V, ψ). Also, it is important to note that another common assumption in fuzzy graphs is that there exists a set of crisp links E, that forces a fuzzy edge to be zero if the corresponding link does not exist in E. Taking into account these considerations, we present the following and simplified definition of a fuzzy graph:

Definition 2. Crisp graph with fuzzy edges [38]. Let G = (V, E) be a graph, and let the function ψ : E ⟶ [0, 1] be a fuzzy set defined over the set of edges, E. The triplet $\tilde{G} = (V, E, ψ)$ is called fuzzy graph or a crisp graph G with fuzzy edges ψ.

Some remarks could be done about the previous definition of a crisp graph with fuzzy edges ψ. The first one is that if a pair of nodes are not adjacent in the crisp graph G, then they can not have any membership degree in ψ. Then, the only available information given by this model is the crisp graph as well as the memberships degree of each pair of adjacent links. Hence, we can see this type of graph as a weighed graph where the weights represent the memberships degree of each pair of links.

In order to give an extended vision of the information, we provide the Definition 2 as an extension of fuzzy graphs, that is far from the notion of valued graphs. First, let us describe another concept which holds the definition of the extended fuzzy graphs.

Definition 3. Fuzzy measure [46]. Given the set V, a fuzzy measure is a set function μ : 2^V ⟶ [0, 1] such that ∀A ⊆ B, then μ (A) ≤ μ (B); μ (∅) =0, and μ (V) =1.

Then, an extended fuzzy graph will be a graph together with a fuzzy measure defined over the set of nodes. Formally:

Definition 4. Extended fuzzy graph [20]. Let G = (V, E) be a graph, and let the function μ : 2^V ⟶ [0, 1] be a fuzzy measure defined over the set of nodes, V. The triplet $\tilde{G} = (V, E, μ)$ is an extended fuzzy graph or crisp graph with fuzzy measure μ.

Now, let us introduce more important concepts, which fix the essentials of this paper.

Definition 5. Möbius transformation [42]. Let f and μ be two real functions defined on the locally finite poset (X, ≤), such that μ (x) = ∑_x≤yf (y); and let the function μ be such that h (x, y) = - ∑_x≤t≤yh (x, t), if x < y; h (x, y) =1, if x = y, and h (x, y) =0 otherwise. Then, the definition of μ (x) depends on the Möbius function h as follows: f (x) = ∑_y≤xh (y, x) μ (y). If we assume that μ is a fuzzy measure, then the function f is the Möbius transformation of μ [18].

Then, we define the k-additivity of a fuzzy measure depending on its Möbius transformation.

Definition 6. k-additivity [17]. Let us assume that the fuzzy measure is defined over the set V = {1, …, n}, and let be k ∈ V = {1, …, n - 1}. The fuzzy measure μ is said to be k-additive if its Möbius transformation is null for all subsets of V with more than k elements. This is, ∀A ⊆ V such that |A| > k, f (A) =0, and ∃K ⊆ V such that |K| = k and f (K) ¬ =0.

Obviously, 1-additive fuzzy measures are additive fuzzy measures. Along this paper we will focus on 2-additive fuzzy measures.

3 Fuzzy measures based on relations

In this section we provide a practical definition of a particular fuzzy measure. Our purpose is to build this fuzzy measure based on a fuzzy relation. Then, let V = {1, …, n} be a finite set of elements, and let us suppose that there is a fuzzy affinity relation between the elements of V. Let us suppose that matrix R characterizes this relation, defining the degree of affinity among each pair of elements of V, in the sense that the element R_ij quantifies the affinity between the individuals i and j. Let us suppose that R is a non-negative, symmetric and normalized matrix whose main diagonal is null. Then, we define μ_R : 2^V ⟶ [0, 1] as follows:

$μ_{R} (S) = \sum_{i, j \in S} R_{ij}$ (1) where R_i,i = 0; R_i,j ≥ 0; R_i,j = R_j,i ∀ i, j ∈ S, and $\sum_{i = 1}^{n} \sum_{j = i}^{n} R_{ij} = 1$ .

Proposition 1. The function μ_R defined in Equation (1) is a fuzzy measure.

Proof. To prove the previous preposition, we check that μ_R holds the characterization of fuzzy measures given in Definition 3.

μ_R (∅) =0 Trivial.

μ_R (V) =1 due to R’s normalization.

μ_R is monotonous ⇔ R_ij ≥ 0. Trivial due to R definition.

Then we show some properties of this fuzzy measure μ_R based on a fuzzy relation.

Proposition 2. μ_R is a 2-additive fuzzy measure.

Proof. This demonstration is based on [17], where it is said that a fuzzy measure μ is 2-additive if and only if we can define it as a linear combination $μ (S) = \sum_{i = 1}^{n} a_{i} x_{i} + \sum_{{i, j} \subset S} a_{ij} x_{i} x_{j}$ , where x_i = 1 if i ∈ S and x_i = 0 otherwise.

Let us define a_i = 0 ∀ i ∈ V, and a_ij = R_ij ∀ {i, j} ⊂ V. Then, according to Equation (1), $μ_{R} (S) = \sum_{i, j \in S} R_{ij} = \sum_{{i, j} \subset V} R_{ij} x_{i} x_{j} = \sum_{i = 1}^{n} a_{i} + \sum_{{i, j} \subset V} a_{ij} x_{i} x_{j}$ .

Proposition 3. μ_R is closed for convex linear combinations as follows:

$μ_{(\sum_{k = 1}^{m} α_{k} {\hat{R}}^{k})} = \sum_{k = 1}^{m} α_{k} μ_{{\hat{R}}^{k}}$ where $\sum_{k = 1}^{m} {\hat{R}}^{k} = R$ and $\sum_{k = 1}^{m} α_{k} = 1$ .

Proof. According to Equation (1), and assuming, x_i = 1 if i ∈ S and x_i = 0 otherwise: $μ_{(\sum_{k = 1}^{m} α_{k} {\hat{R}}^{k})} = \sum_{i, j \in S} (\sum_{k = 1}^{m} α_{k} {\hat{R}}_{ij}^{k}) x_{i} x_{j}$ $= \sum_{k = 1}^{m} \sum_{i, j \in S} α_{k} {\hat{R}}_{ij}^{k} x_{i} x_{j} =$ $\sum_{k = 1}^{m} α_{k} \sum_{i, j \in S} {\hat{R}}_{ij}^{k} x_{i} x_{j} = \sum_{k = 1}^{m} α_{k} μ_{{\hat{R}}^{k}}$

Remark 1. A particular case of Proposition 3 is that μ_R is fixed for the mean: $\frac{μ_{R^{1}} + μ_{R^{2}}}{2} = μ_{\frac{R^{1} + R^{2}}{2}}$

3.1 The graph associated with a fuzzy measure

Let μ be a fuzzy measure which defines some affinity relation between all the pairs of elements of a finite set V. In this subsection we define the weighted graph associated with μ. Its definition is based on the Shapley value [44] as follows: for each pair of elements i, j, we quantify how the absence of one individual affects the other element of the pair by means of the value F_ij:

$F_{ij} = φ ({Sh}_{i} (μ) - {Sh}_{i}^{j} (μ), {Sh}_{j} (μ) - {Sh}_{j}^{i} (μ))$ (2) where φ : [-1, 1] ⟶ [0, 1] is a bi-variate aggregation operator [50]; Sh_i (μ) is the Shapley value of the node i in the presence of all the nodes depending on μ, and ${Sh}_{i}^{j} (μ)$ is the Shapley value of the node i in the presence of all the nodes except the node j according to their relation in μ. Then, the weighted graph associated with the fuzzy measure μ is that whose adjacency matrix is F (see Equation (2)).

The calculation of Shapley value has exponential complexity, which could be moderately solved with some sampling techniques (see [6, 7] for further information). However, when additive fuzzy measures are considered, this calculation is immediate. According to Proposition 2, and under the assumption that the matrix R characterizes the affinity relations among the nodes, the fuzzy measure μ_R obtained from R following Equation (1) is 2-additive, so the calculation of the Shapley value does not imply any complexity increasing.

Proposition 4. The fuzzy measure obtained from matrix R according to Equation (1), μ_R, holds the following:

${Sh}_{i} (μ_{R}) = \sum_{k \neq i k \in V} R_{ik}$

${Sh}_{i}^{j} (μ_{R}) = \sum_{k \neq i k \in V ∖ {j}} R_{ik} = (\sum_{k \neq i k \in V} R_{ik}) - R_{ij}$

Proof. We will demonstrate the point 1. According to [7], for every individual i, its Shapley value can be rewritten as the average of the marginal contributions in all its orders. It is, ${Sh}_{i} = \frac{1}{n!} \sum_{o \in π (n)} [μ (pred (i) + {i}) - μ (pred (i))]$ According to Equation (1), $μ (pred (i) + {i}) = \sum_{k = 1 k \neq i}^{n} \sum_{j = 1 j \neq i}^{n} R_{jk} x_{j} x_{k} + \sum_{k = 1}^{n} (R_{ik} + R_{ki}) x_{k}$ $μ (pred (i)) = \sum_{k = 1 k \neq i}^{n} \sum_{j = 1 j \neq i}^{n} R_{jk} x_{j} x_{k}$ being x_j = 1 if j ∈ pred (i) , and x_j = 0 otherwise. Hence, ${Sh}_{i} = \frac{1}{n!} \sum_{o \in π (n)} (\sum_{k = 1 k \neq i}^{n} \sum_{j = 1 j \neq i}^{n} R_{jk} x_{j} x_{k} + \sum_{k = 1}^{n} (R_{ik} + R_{ki}) x_{k})$ $- (\sum_{k = 1 k \neq i}^{n} \sum_{j = 1 j \neq i}^{n} R_{jk} x_{j} x_{k}) =$ $\frac{1}{n!} \sum_{o \in π (n)} \sum_{k = 1}^{n} (R_{ik} + R_{ki}) x_{k}$

For a half of o ∈ π (n), k ∈ pred (i), then, for a half of the values of previous summation, it is held that x_k = 1. Hence,

$\frac{1}{n!} \sum_{o \in π (n)} \sum_{k = 1}^{n} (R_{ik} + R_{ki}) x_{k} = \frac{1}{2} \sum_{k = 1}^{n} (R_{ik} + R_{ki}) x_{k}$

Due to R’s simmetry, R_ik = R_ki. Moreover, R_ii = 0. Then

$\frac{1}{2} \sum_{k = 1}^{n} (R_{ik} + R_{ki}) x_{k} = \frac{1}{2} \sum_{k = 1}^{n} 2 R_{ik} x_{k} = \sum_{k = 1}^{n} R_{ik} x_{k} = \sum_{k \neq i k \in V} R_{ik}$

Then, the demonstration of point 2 is analogous.

The following proposition is an immediate consequence of Proposition 4.

Proposition 5. Let μ_R be the fuzzy measure obtained from the matrix R following Equation (1). Then, for each pair of elements i, j, the following points are held: $1 . {Sh}_{i} (μ_{R}) - {Sh}_{i}^{j} (μ_{R}) = R_{ij}$ $2 . {Sh}_{j} (μ_{R}) - {Sh}_{j}^{i} (μ_{R}) = R_{ji}$

Proof. According to Proposition 4, $1 . {Sh}_{i} (μ_{R}) - {Sh}_{i}^{j} (μ_{R}) = \sum_{k \neq i k \in V} R_{ik} - (\sum_{k \neq i k \in V} R_{ik} - R_{ij})$ $= \sum_{k \neq i k \in V} R_{ik} - \sum_{k \neq i k \in N} R_{ik} + R_{ij} = R_{ij}$

The proof of point 2 is analogous.

Hence, we can define the affinity between each pair of nodes as $F_{ij} = φ ({Sh}_{i} - {Sh}_{i}^{j}, {Sh}_{j} - {Sh}_{j}^{i}) = φ (R_{ij}, R_{ji})$ .

An alternative definition of the affinity between a pair of nodes{i, j} is related to the interaction index proposed by Grabisch [17].

$I_{ij} = \sum_{k = 0}^{n - 2} ζ_{k} \sum_{K \subset V ∖ {i, j} | K | = k} (μ_{ijK} - μ_{iK} - μ_{jK} + μ_{K})$ (3) $where ζ_{k} = \frac{(n - k - 2)! k!}{(n - 1)!} = \frac{1}{(\begin{matrix} n - 2 \\ k \end{matrix}) (n - 1)}$

Proposition 6. For each pair of nodes {i, j}, the interaction index of μ_R, I_ij, is F_ij, considering φ = sum (| . |, | . |) in Equation (2).

Proof. To make easier the follow up of this proof, let us introduce some notation. $a = \sum_{l \in K l \neq i, j} \sum_{s \in K s \neq i, j s > l} 2 R_{ls} b = \sum_{l \in K l \neq i, j} 2 R_{li} c = \sum_{l \in K l \neq i, j} 2 R_{lj}$

Then, according to Equation 1, we can rewrite the components of the interaction index as follows:

$μ_{ijK} = a + b + c + 2 R_{ij} μ_{iK} = a + b$

$μ_{jK} = a + c μ_{K} = a$

Hence, $I_{ij} = \sum_{k = 0}^{n - 2} ζ_{k} \sum_{K \subset V ∖ {i, j} | K | = k} (μ_{ijK} - μ_{iK} - μ_{jK} + μ_{K}) = \sum_{k = 0}^{n - 2} ζ_{k} \sum_{K \subset V ∖ {i, j} | K | = k} (a + b + c + 2 R_{ij}) - (a + b) - (a + c) + a = \sum_{k = 0}^{n - 2} ζ_{k} \sum_{K \subset V ∖ {i, j} | K | = k} 2 R_{ij} = \sum_{k = 0}^{n - 2} \frac{1}{(\begin{matrix} n - 2 \\ k \end{matrix}) (n - 1)} (\begin{matrix} n - 2 \\ k \end{matrix}) 2 R_{ij} = \sum_{k = 0}^{n - 2} \frac{1}{n - 1} 2 R_{ij} = 2 R_{ij} = R_{ij} + R_{ji} = ({Sh}_{i} - {Sh}_{i}^{j}) + ({Sh}_{j} - {Sh}_{j}^{i}) = φ ({Sh}_{i} - {Sh}_{i}^{j}, {Sh}_{j} - {Sh}_{j}^{i})$ , when φ = sum.

4 A modification of the Louvain algorithm for its application in extended fuzzy graphs

The problem of finding a good partition for a given graph is known as Community Detection Problem. In the classical version of this problem, each node just belongs to one community, this is, only non overlapping partitions are allowed [31]. However, we can find in the literature several variations of it, in which nodes can belong to more than one community can be found in [8 , 51].

In this work we propose a new concept of a group which is based on the notion of the extended fuzzy graphs (see Section 2). Hence, under the assumption that $\tilde{G} = (V, E, μ)$ is an extended fuzzy graph in which μ defines some affinity relation among the elements of V, we consider that a group is composed of those nodes that are tightly-knit connected in E and between which there are a strong affinity relation given by μ.

In this section we show a modification of the Louvain algorithm [4], which can deal with different information sources when solving community detection problems.

The Louvain algorithm has two key points in its performance. One of these points is the search of ‘possible’ clusters, finding for each node in the graph all its neighbours (we say ‘possible’ clusters because two nodes can not be in the same module if they are not connected). The other point is about the calculation of the modularity variation that takes place when a node is moved from its community to another. Both points are faced with the support of the adjacency matrix of the graph, which is the input parameter of this algorithm. Nevertheless, we propose a new vision of this method, assuming it has two input parameters, with different purposes: one is devoted to connection analysis and other is devoted to modularity calculation. This approach is summarized in Algorithm 1.

Then, our proposed community detection algorithm is based on this vision of the method with two input parameters. The main aim of our method is to find community structures in networks, not only considering the structure of the graph, as classical methods do, but also with the analysis of any other type of information. Let A be the adjacency matrix of the graph G = (V, E), and let $M$ be any matrix. Let ΔQ_i (j) be the variation of modularity obtained when moving the node i to j’s community [4]. Duo Louvain Algorithm is defined in following pseudocode.

Algorithm 1 Additional Louvain input= $(A, M)$ output=P

1: ∀i ∈ V, let i be an isolated community

2: o = permutation (V)

3: for k ∈ o do

4: search in A all the neighbours of k, j

5: ∀j, calculate ΔQ_k (j) in matrix $M$

6: $j^{*} = {j | Δ Q_{k} (j^{*}) = max_{j} {Q_{k} (j)}}$

7: if ΔQ_k (j^*) >0 then

8: Move node k to j^* ’s community

9: else

10: k remains in its community

11: end if

12: end for

Algorithm 2 Duo Louvain input= $(A, M)$ output=P

1: P₁ is a single-community partition with all the vertices

2: P₂ is a partition of V such that ∀i ∈ V, i is an isolated community in P₂.

3: A₁ = A, A₂ = A, $M_{1} = M$ , $M_{2} = M$

4: while P₁ ¬ = P₂ do

5: P₁ = P₂

6: P₂= $Additional_Louvain (A_{2}, M_{2})$ .

7: A₂ is the aggregated matrix obtained from the network A₁, whose nodes are the communities of P₂.

8: $M_{2}$ is the aggregated matrix obtained from the network $M_{1}$ , whose nodes are the communities of P₂.

9: A₁ = A₂, $M_{1} = M_{2}$

10: end while

11: P = P₂

Let us remark that the application of Duo_Louvain(A, A), using the adjacency matrix for both input parameters, is exactly equal as the application of the Louvain algorithm over the matrix A. Furthermore, the complexity of our proposal is the same as the Louvain algorithm’s complexity is.

Thus far we have not questioned the origin of matrix $M$ . It may be any matrix giving some extra information about the nodes. It may also be the adjacency matrix, as we have mentioned previously. Or even, a combination of some additional information, $M^{a}$ , with the adjacency matrix, A (for example, $M = θ (M^{a}, A)$ being $θ : X^{2} ⟶ X$ an aggregation function [19] defined over the set of quadratic n-matrices $X$ , used to aggregate two matrices into one.

Then, we explain how to adapt Duo Louvain Algorithm for its application in community detection problems over extended fuzzy graphs. In this framework, the additional matrix will be related to the corresponding fuzzy measure. Let $\tilde{G} = (V, E, μ_{R})$ be an extended fuzzy graph [20], where the fuzzy measure μ_R defines some affinity relation between the elements of V (see Section 3). Duo Affinity Louvain Algorithm, summarized in Algorithm 3, is a particular application of Duo Louvain Algorithm to find communities based on affinity in $\tilde{G}$ .

Algorithm 3 Duo Affinity Louvain input=(A, μ) output=P

1: $F_{ij} = φ ({Sh}_{i} (μ) - {Sh}_{i}^{j} (μ), {Sh}_{j} (μ) - {Sh}_{j}^{i} (μ))$

2: $M = θ {A, F}$

3: Duo_Louvain( $A, M$ )

Assuming that μ_R is built from the matrix R according to Equation (1), $F_{ij} = φ (R_{ij}, R_{ji})$ ∀i, j ∈ V. Let us note that, because of R’s symmetry, there is a wide set of possible aggregation operators φ as for example the mean, the minimum, the maximum or the median, such that F_ij = R_ij. With this type of aggregation φ, trivially, Duo _ Affinity _ Louvain (A, μ_R) = Duo _ Louvain (A, θ (A, R)). Let us remark that μ_R is a 2-additive fuzzy measure built from n² data structure.

Let us recall the example proposed in the Introduction. Now we show that the Algorithm 3, Duo Affinity Louvain detects the communities which seemed to be logical when considering the political point of view of the individuals.

Example 1. Let μ_R be the additive fuzzy measure built from matrix R, and let $\tilde{G} = (V, E, μ_{R})$ be the extended fuzzy graph whose adjacency matrix is that showed in Fig. 2a. Regarding O, the vector of political opinion proposed in the Introduction, let R (Fig. 2b) be the matrix representing the affinity relations between the individuals depending on their political point of view. We assume that those individuals who share their political opinion have strong affinity relations, whereas those individuals whose political opinion is opposite do not have affinity.

Fig. 2

Extended Fuzzy Graph $\tilde{G} = (V, E, μ_{R})$ .

Considering $θ (A, R) = \frac{1}{2} A + \frac{1}{2} R$ , the partition obtained with the application of the Algorithm 3, Duo Affinity Louvain, is $P^{a} = {{1, 2, 3}, {4, 5}, {6, 7}, {8, 9, 10}}$ . However, if we just pay attention to the topology of the graph, the partition obtained with the Louvain algorithm is $P = {{1, 2, 3, 4, 5}, {6, 7, 8, 9, 10}}$ .

5 Computational results

5.1 Benchmark graphs

One of the most important points to compare different methods besides their complexity or speed, is the quality metric used to measure the goodness of obtained groups. There are a lot of measures to test the ‘goodness’ of a partition, as for example, the modularity [40] or the centrality degree [26]. Another type of metrics have been deeply studied by means of the performance of clustering algorithms in ‘benchmark graphs’ [30]. Benchmark graphs are artificial graphs built with a known clustering structure integrated in the network by construction. This structure is considered the ‘standard’ that any community detection algorithm should find. Under the assumption that the expected degree of each node, <k>, and the community size of each cluster, |C_t|, are power laws with exponents α and β, the construction of benchmark graphs is based on the Equation (4): given the cluster C_t, for each pair of nodes (i, j), there will be a link between them with the probability defined below.

$P (i, j) = {\begin{matrix} α & if & i, j \in C_{t} \\ β & if & otherwise \end{matrix}$ (4)

A clustering method is as good as its ability to detect this fixed structure is good: the best algorithm will be the one which provides a clustering structure as similar as possible to the standard.

This similarity between the standard structure and the obtained partition is usually measured with the normalized mutual information NMI [29].

5.2 Results

In this work, we empirically analyze the performance of our community detection algorithm based on extended fuzzy graphs, Duo Affinity Louvain Algorithm, by means of its performance in four different benchmark graphs, following the idea proposed in [15].

Each benchmark graph, representing the extended fuzzy graph $\tilde{G} = (V, E, μ_{R})$ , will have two different parts. One is related to the graph G = (V, E) that defines the edges or direct connections among nodes. The other is related to the relation of affinity among the nodes. This second part, is defined by means of a fuzzy measure μ_R which is built from a matrix R which characterizes the degree of affinity among the nodes. Regarding Subsection 3.1, R is the adjacency matrix of the weighted graph associated with μ_R. Hence, considering φ = min, Duo _ Affinity _ Louvain (A, μ_R) = Duo _ Louvain (A, R).

To build these two matrices randomly, A and R, different values of in/out degree (z_in and z_out respectively) will be considered, as can be seen in Table 1. Both networks will be generated according to the Equation (4). The standard partition will depend on the benchmark graph considered.

Table 1
Benchmark Parameters

Label α β

1 0.45 0.016

2 0.4 0,033

3 0.35 0.05

4 0.325 0.058

5 0.3 0.066

6 0.275 0.075

7 0.25 0.083

8 0.225 0.091

9 0.2 0.1

Label	α	β
1	0.45	0.016
2	0.4	0,033
3	0.35	0.05
4	0.325	0.058
5	0.3	0.066
6	0.275	0.075
7	0.25	0.083
8	0.225	0.091
9	0.2	0.1

Hence, we propose the generation of four different benchmark models, as can be seen in Figs. 3, 4, 5, 6, all based on the idea about the construction of synthetic or benchmark graphs proposed in [15]. We assume that nodes in the boxes of the ‘main’ diagonal of each relation network have high affinity degree, it is, a strong relation in μ_R. In the same sense, nodes in the boxes of the ‘main’ diagonal of each adjacency graph are tightly-knit connected. Following the idea of group given in Section 4, when possible, connected nodes with a strong good relation should be in the same module.

Fig. 3

Benchmark Model. Case 1.

Fig. 4

Benchmark Model. Case 2.

Fig. 5

Benchmark Model. Case 3.

Fig. 6

Benchmark Model. Case 4.

In this work we empirically test the performance of our method. Hence, we analyze several linear aggregations of corresponding matrices, $M = θ (A, R) = γ A + (1 - γ) R$ , considering different values for the aggregation parameter γ, (γ = 1, 0.75, 0.5, 0.25, 0). In Tables 2, 3, 4, 5, we show an average of the NMI resulting from 100 iterations of each combination of the values α and β for both networks, generated with 256 nodes, when γ = 0 (in this case, the results are optimal for all the benchmarks).

Table 2

NMI. Benchmark Model Case 1

NMI	Relations Value 1	Relations Value 2	Relations Value 3	Relations Value 4	Relations Value 5	Relations Value 6	Relations Value 7	Relations Value 8	Relations Value 9
Graph Value 1	1	1	1	1	1	1	0.9966	0.9473	0.8022
Graph Value 2	1	1	1	1	1	1	0.995	0.9267	0.7999
Graph Value 3	1	1	1	1	1	0.9999	0.994	0.9238	0.8043
Graph Value 4	1	1	1	1	1	1	0.9963	0.9237	0.7998
Graph Value 5	1	1	1	1	1	0.9996	0.9963	0.9335	0.7986
Graph Value 6	1	1	1	1	1	0.9996	0.9951	0.9206	0.8004
Graph Value 7	1	1	1	1	1	0.9994	0.9949	0.9258	0.8011
Graph Value 8	1	1	1	1	1	0.9997	0.9945	0.922	0.7958
Graph Value 9	1	1	1	1	1	0.9999	0.9953	0.9263	0.7973

Table 3

NMI. Benchmark Model Case 2

NMI	Relations Value 1	Relations Value 2	Relations Value 3	Relations Value 4	Relations Value 5	Relations Value 6	Relations Value 7	Relations Value 8	Relations Value 9
Graph Value 1	1	1	1	1	0.9985	0.9912	0.9842	0.9984	0.999
Graph Value 2	1	1	1	1	0.9993	0.9939	0.9936	0.9982	0.996
Graph Value 3	1	1	1	1	0.9986	0.9931	0.9958	0.9941	0.9931
Graph Value 4	1	1	1	1	0.9999	0.9963	0.9963	0.9916	0.9871
Graph Value 5	1	1	1	1	0.9997	0.9925	0.9957	0.9969	0.9895
Graph Value 6	1	1	1	1	0.9985	0.9984	0.9937	0.9907	0.9904
Graph Value 7	1	1	1	1	0.9995	0.9951	0.9962	0.9828	0.9946
Graph Value 8	1	1	1	1	0.9991	0.9932	0.9894	0.9924	0.9873
Graph Value 9	1	1	1	1	1	0.9965	0.9967	0.9837	0.9877

Table 4

NMI. Benchmark Model Case 3

NMI	Relations Value 1	Relations Value 2	Relations Value 3	Relations Value 4	Relations Value 5	Relations Value 6	Relations Value 7	Relations Value 8	Relations Value 9
Graph Value 1	1	1	0.9998	0.9997	0.9994	0.9942	0.962	0.9105	0.8516
Graph Value 2	1	1	0.9996	0.9995	0.9977	0.9927	0.968	0.8958	0.8409
Graph Value 3	1	1	0.9998	0.999	0.9996	0.9936	0.9719	0.8837	0.8389
Graph Value 4	1	1	0.9997	0.9995	0.9988	0.9947	0.9598	0.8868	0.8408
Graph Value 5	1	1	0.9998	0.9995	0.9982	0.9914	0.9686	0.8873	0.8411
Graph Value 6	1	1	0.9995	0.9987	0.9979	0.991	0.9703	0.8816	0.8442
Graph Value 7	1	1	0.9996	0.9997	0.9989	0.9944	0.9651	0.8829	0.8411
Graph Value 8	0.9999	1	0.9999	0.9997	0.9992	0.9974	0.9569	0.8845	0.842
Graph Value 9	0.9999	0.9999	0.9998	0.9994	0.9997	0.9935	0.9616	0.8824	0.8485

Table 5

NMI. Benchmark Model Case 4

NMI	Relations Value 1	Relations Value 2	Relations Value 3	Relations Value 4	Relations Value 5	Relations Value 6	Relations Value 7	Relations Value 8	Relations Value 9
Graph Value 1	0.9996	0.999	0.997	0.9979	0.9971	0.9987	0.9896	0.9803	0.9881
Graph Value 2	0.9997	0.9996	0.9958	1	0.9963	0.9949	0.9944	0.9733	0.9805
Graph Value 3	0.9996	0.999	0.9976	0.9999	0.9994	0.9979	0.9918	0.9828	0.9794
Graph Value 4	0.9994	0.9993	0.9991	1	0.9959	0.994	0.9851	0.9745	0.969
Graph Value 5	1	1	0.9981	1	0.9978	0.998	0.9858	0.9757	0.9695
Graph Value 6	0.9998	1	0.9997	1	1	0.9891	0.9915	0.9721	0.9686
Graph Value 7	0.9994	0.9997	1	1	1	0.9939	0.9827	0.9787	0.9654
Graph Value 8	0.9987	1	1	0.9975	1	0.9895	0.9872	0.9725	0.9628
Graph Value 9	0.9999	1	0.9979	1	0.9949	0.9869	0.9802	0.9705	0.9591

5.2.1 Benchmark model. Case 1

Now we show the performance of our algorithm in the most basic case. Here, the relations graph is defined in the same way as it was done in [15], considering 256 nodes. Regarding the structure of the graph, in matrix A₁ the nodes are organized into 2 modules whose expected size is $| C_{i}^{A} | = 128$ , and the expected degree of each node is <k > =128α + 128β. Regarding the relations, nodes in matrix R₁ are organized into 4 communities, $C_{1}^{R}, \dots, C_{4}^{R}$ , where $| C_{i}^{R} | = 64 \forall i$ ; and, for each node the expected degree is <k > =64αα + 192αβ = 32.

Obtained results for different values of α and β (in Table 1 we can see the label assigned for each value of these parameters) are shown in Table 2.

5.2.2 Benchmark model. Case 2

In this subsection we show the performance of our algorithm in a more complex structure. Now the ‘gold’ structure is finer than it is in the situation showed in Subsection 5.2.1. In this case, the graph is organized into 4 clusters, where $| C_{i}^{A} | = 64$ , and the expected degree of each node is <k > =64αα + 192αβ = 32. The matrix of relations R₂ has 8 clusters whose expected size is $| C_{i}^{R} | = 32$ , and the expected degree of each node is <k > =32αα + 224αβ. Let us note that, even though the Louvain algorithm is very size sensitive, our proposal works very well, as it can be seen in Table 3.

5.2.3 Benchmark model. Case 3

In this subsection we apply our algorithm in a more complex situation: we broke the symmetry of the structure in the relations matrix R₃, hindering the clustering process (see Fig. 5) Then, the expected size of these 5 clusters is $| C_{1}^{R} | = 42$ , $| C_{2}^{R} | = 43$ , $| C_{3}^{R} | = 43$ , $| C_{4}^{R} | = 88$ , $| C_{5}^{R} | = 40$ . Regarding the adjacency matrix A₃, it is built in the same way as it is built matrix A₁ in Subsection 5.2.1. Despite the complexity of this structure in which there are different sizes communities, in Table 4 we show that our method still works very well.

5.2.4 Benchmark model. Case 4

Finally, we increment the complexity of the framework. Not only the structure of the relation network is asymmetric, but the communities of the graph are somewhat small (see Fig. 6). The adjacency matrix A₄ is built in the same way as it is built matrix A₂ in Subsection 5.2.2. Regarding the relations matrix R₄, it is built with 8 embedded clusters, whose expected sizes are $| C_{1}^{R} | = 40$ , $| C_{2}^{R} | = 24$ , $| C_{3}^{R} | = 32$ , $| C_{4}^{R} | = 32$ , $| C_{5}^{R} | = 64$ , $| C_{6}^{R} | = 21$ , $| C_{7}^{R} | = 22$ and $| C_{8}^{R} | = 21$ . Despite this complex structure, our algorithm provides very good results, (see Table 5), being able to recover the information of the cluster embedded in the standard successfully.

6 Conclusions and further research

Graphs are used to model and visualize the existing relationships between a set of objects. However, in real-life problems there is always some extra information which is not represented by graphs. Hence, graphs are not enough for modeling those situations in which there is some additional information apart from relationships. Here lies the importance of considering networks including additional information. Then, our proposal is based on the use of extended fuzzy graphs.

The main aim of this work is related to community detection problems over extended fuzzy graphs [20]. We can summarize it as the search of community structures in problems modeled with a network in which there exists some additional information apart from the structure of the graph. This type of situation is defined by means of an extended fuzzy graph, G = (V, E, μ), where μ is a fuzzy measure defining some affinity relation among the elements of V, which is not inherent to the structure of the graph.

To carry on with it, first we do a recall of some basic concepts about fuzzy framework. We provide the definition of extended fuzzy graphs, a triplet $\tilde{G} = (V, E, μ)$ consisting on a graph together with a fuzzy measure. Let us remark that there is a great difference between fuzzy graphs and extended fuzzy graphs. In fuzzy graphs, two nodes that are not adjacent in the crisp graph G, can not have any membership degree in the fuzzy measure μ. For this reason, the information is just given by the crisp graph and the membership degree of each adjacent edge, so we can see a fuzzy graph as a particular weighted graph. However, in extended fuzzy graphs, all the pairs of nodes in V have some relation in μ, regardless of whether they are connected or not in E.

Apart of these contributions, we propose a particular definition of a fuzzy measure μ_R based on matrix R which defines some affinity relation. We also demonstrate different properties of μ_R, for example, it is a 2-additive fuzzy measure. Then, we define the weighted graph associated with a fuzzy measure. It is the key point of the algorithm that we propose to deal with community detection problems over extended fuzzy graphs, in which there exists some additional information defined by a fuzzy measure that is related to the affinity relation among the nodes.

Then, we suggest a modification of the Louvain algorithm [4], called Duo Louvain Algorithm, which can manage several information sources when dealing with community detection problems. This proposal has the same computational complexity as the Louvain method. Moreover, it supposes a valuable way to find good partitions. We also provide a particular application of Duo Louvain Algorithm to work with extended fuzzy graphs, Duo Affinity Louvain Algorithm. This algorithm provides a community structure in which the nodes assigned to the same group have high affinity degree. For the specific case of a fuzzy measure built from a fuzzy relation (see Section 3), we show that its application is immediate. In fact, the only input parameters of the algorithm here proposed are a graph and a relation matrix related to the nodes, it is, two matrices (n x n). This basic framework allows us to model great complexity problems that had not been possible to address until now. Also, let us remark the importance of working with simple fuzzy measures as the one here proposed (2-additive). The ‘low’ complexity in its formulation, allow us to model in a quite simple way real situations.

It is easy to imagine a background application for the problem here proposed. Just imagine a set of people with several physical connections, which have different affinities depending on their political opinion or hobbies. More examples can be found in social networks or microblogging services, such as Twitter. In this context, we can see the different pairwise of users as a network in which there is a link between two profiles (nodes) if they follow each other. We can assume that this type of information defines the structure of a graph. Obviously, the footprint of the user’s profiles is much more rich than it: taking a look to the social interactions, such tweeting, or the textual information, such as tweets, retweets or hashtags, we can obtain a rich source of knowledge about how users are related and how they should be grouped, beyond the existing links in the network. Some researches under this starting point can be found in [2 , 35].

To finish, let us remark that this contribution provides a great improvement with respect to the classical community detection. Although some good ideas have been proposed along the years to include some extra information in clustering problems [3 , 43], all of them just consider the topology of the graph with a pre-processing step or similar strategies.

In this work we also show the performance of our proposal in several benchmark models [1] with different levels of complexity. As we show in Section 5, the performance of our algorithm is excellent. In Tables 2, 3, 4, 5 we provide the average of the calculation of the NMI [28] of obtained partitions for 100 iterations of each case. As it can be seen, it is almost 1 in all the situation. These values allows us to affirm that our method guarantees very good results in solving clustering problems with additional information.

As further research, we will work in the develop of our idea considering different fuzzy measures (the bipolar case was analyze with a simple example in [21]). We will also study some properties of the fuzzy measure and we will apply it in a real-case example, a database extracted from Twitter. Other work direction is about the inclusion of the additional information in others clustering methods, such as the Girvan-Newman algorithm defined in [15].

Acknowledgments

This research has been partially supported by the Government of Spain, Grant Plan Nacional de I+D+i, MTM2015-70550-P, PGC2018096509-B-I00 and TIN2015-66471-P.

References

Bader

, Kappes

, Meyerhenke

, Sanders

, Schulz

and Wagner

, Benchmarking for graph clustering and partitioning, Encyclopedia of Social Network Analysis and Mining (2017).

Bhuvaneswari

and Valliyammai

, Information Entropy based event detection during disaster in cybersocial networks, Journal of Intelligent and Fuzzy Systems 36(5) (2019), 3981–3992.

de Blas

C.S.

, Martin

J.S.

and Gomez

, Combined social networks and data envelopment analysis for ranking, European Journal of Operational Research 266(3) (2018), 990–999.

Blondel

, Guillaume

, Lambiotte

and Lefevre

, Fast unfolding of communities in large networks, Journal Of Statistical Mechanics-Theory And Experiment (P10008) (2008).

Bock

, Automatische Klassifikation. Vadenhoeck Ruprecht, Gottingen, Zurich. (1974).

Castro

, Gómez

, Molina

and Tejada

, Improving polynomial estimation of the shapley value by stratified random sampling with optimum allocation, & Operations Research 82 (2017), 108–188.

Castro

, Gómez

and Tejada

, Polynomial calculation of the shapley value based on sampling, & Operations Research 36(5) (2009), 1726–1730.

Chang

, Li

, Juang

, Li

and Zhao

, An algorithm to find overlapping community structure in networks, Journal of Intelligent and Fuzzy Systems 36(6) (2019), 5167–5175.

Chen

, Jiao

, Zhang

, Liu

, Feng

and Wang

, Tripimputor: Real-time imputing taxi trip purpose leveraging multi-sourced urban data, IEEE Transactions on Intelligent Transportation Systems 19(10) (2018), 3292–3304.

10.

Chouchani

and Abed

, Online social network analysis: detection of communities of interest, Journal of Intelligent Information Systems 54(1) (2020), 5–21.

11.

De Meo

, Nocera

, Terracina

and Ursino

, Recommendation of similar users, resources and social networks in a social internet working scenario, Information Sciences 181(7) (2011), 1285–1305.

12.

Devarajan

, Fatima

, Vairavasundaram

and Ravi

, Swarm intelligence clustering ensemble based point of interest recommendation for social cyber-physical systems, Journal of Intelligent and Fuzzy Systems 36(5) (2019), 4349–4360.

13.

Fortunato

, Community detection in graphs, Physics Reports-Review Section of Physics Letters 486(3-5) (2010), 75–174.

14.

Friedkin

, Horizons of observability and limits of informal control in organization, Social Forces 62(1) (1983), 55–77.

15.

Girvan

and Newman

, Community structure in social and biological networks, Proceedings of the National Academy of Sciences 99(2) (2002), 7821–7826.

16.

Gómez

, González-Arangüena

, Manuel

, Owen

, del Pozo

and Tejada

, Centrality and power in social networks: a game theoretic approach, Mathematical Social Scientes 46(1) (2003), 27–54.

17.

Grabisch

, k-order additive discrete fuzzy measures and their representation, Fuzzy Sets Systems 92(2) (1997), 167–189.

18.

Grabisch

and Labreuche

, Bi-capacities part i: definition, möbius transform and interaction, Fuzzy Sets and Systems 151(2) (2005), 211–236.

19.

Grabisch

, Marichal

J.L.

, Mesiar

and Pap

, Aggregation functions: Construction methods, conjunctive, disjunctive and mixed classes, Information Science 181 (2011), 23–43.

20.

Gutiérrez

, Gómez

, Castro

and Espínola

, A new community detection algorithm based on fuzzy measures. In: C. Kahraman, S. Cebi, Cevik S. Onar, B. Oztaysi, A. Tolga, Sari, I. (eds.) Advances in Intelligent Systems and Computing series. vol. 1029. Intelligent and Fuzzy Techniques in Big Data Analytics and Decision Making. INFUS 2019, Springer, Cham (2020).

21.

Gutiérrez

, Gómez

, Castro

and Espínola

, A new community detection problem based on bipolar fuzzy measures, Studies in Computational Intelligence (2020).

22.

Hajek

, Wu

and Xu

, Information limits for recovering a hidden community, IEEE Transactions on Information Theory 63(8) (2017), 4729–4745.

23.

Hewapathirana

, Change detection in dynamic attributed networks, Wiley Interdisciplinary Reviews-Data Mining and Knowledge Discovery 9(3), e1286 (2019).

24.

Hrabcak

, Matis

, Dobos

and Papaj

, Tools for evaluation of social relations in mobility models, Telecommunication systems 68(3) (2018), 409–424.

25.

Javed

, Younis

, Latif

, Qadir

and Baig

, Community detection in networks: A multidisciplinary review, Journal of Network and Computer Applications 108 (2018), 87–111.

26.

Katz

, A new index derived from sociometrical data analysis, Psychometrika 18 (1953), 39–43.

27.

Kianian

, Khayyambashi

and Movahhedinia

, Fuseo: Fuzzy semantic overlapping community detection, Journal of Intelligent and Fuzzy Systems 32(6) (2017), 3987–3998.

28.

Kvalseth

, On normalized mutual information: Measure derivations and properties, Entropy 19(11) (2017).

29.

Lancichinetti

and Fortunato

, Community detection algorithms: A comparative analysis, Physical Review E 80(056117) (2009).

30.

Lancichinetti

, Fortunato

and Radicchi

, Benchmark graphs for testing community detection algorithms, Physical Review E 78(046110) (2008).

31.

Lancichinetti

, Radicchi

, Ramasco

and Fortunato

, Finding statistically significant communities in networks, PloS One 6(4) (2011).

32.

, Cerrada

, Cabrera

, Sánchez

, Pacheco

, Ulutagay

and de Oliveira

, A comparison of fuzzy clustering algorithms for bearing fault diagnosis, Journal of Intelligent and Fuzzy Systems 34(6) (2018), 3565–3580.

33.

, Detecting fuzzy network communities based on semi-supervised label propagation, Journal of Intelligent and Fuzzy Systems 31(6) (2016), 2887–2893.

34.

Liu

, Zhou

, Huang

, Li

and Ju

, Combining similarity and divergence measures for intuitionistic fuzzy information clustering, Journal of Intelligent and Fuzzy Systems 36(4) (2019), 3195–3209.

35.

López-Ramírez

, Molina-Villegas

and Siordia

, Geographical aggregation of microblog posts for lda topic modeling, Journal of Intelligent and Fuzzy Systems 36(5) (2019), 4901–4908.

36.

, Li

, Tan

and Huang

, Detecting evolving communities in dynamic networks using graph regularized evolutionary nonnegative matrix factorization, Physica A-Statistical Mechanics and its Application 530, 121279 (2019).

37.

Majhi

, Bhatachharya

, Pradhan

and Biswal

, Fuzzy clustering using salp swarm algorithm for automobile insurance fraud detection, Journal of Intelligent and Fuzzy Systems 36(3) (2019), 2333–2344.

38.

Mordeson

and Nair

, Fuzzy graphs, Studies in Fuzziness and Soft Computing 46 (2000), 19–81.

39.

Newman

, Finding community structure in networks using the eigenvectors of matrices, Physical Review E 74(036104) (2006).

40.

Newman

and Girvan

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

41.

Rosenfeld

, Fuzzy graphs (1975).

42.

Rota

, On the foundations of combinatorial theory i. theory of möbius functions, Z. Wahrseheinlichkeitstheorie 2 (1964), 340–368.

43.

Saad

and Nosratinia

, Community detection with side information: Exact recovery under the stochastic block model, IEEE Journal of Selected Topics in Signal Processing 12(5) (2018), 944–958.

44.

Shapley

, A value for-person games. Contribute Theory Games 2(28) (1953), 307–317.

45.

Springel

, Pakmor

, Pillepich

, Weinberger

, Nelson

, Hernquist

, Vogelsberger

, Genel

, Torrey

, Marinacci

and Naiman

, First results fromthe illustris TNG simulations: matter and galaxy clustering, Monthly Notices of the Royal Astronomical Society 475(1) (2018), 676–698.

46.

Sugeno

, Fuzzy measures and fuzzy integrals: A survey, Fuzzy Automata Decision Process 78 (01 1977).

47.

Thao

, Ali

and Smarandache

, An intuitionistic fuzzy clustering algorithm based on a new correlation coefficient with application in medical diagnosis, Journal of Intelligent and Fuzzy Systems 36(1) (2019), 189–198.

48.

and Chiclana

, A social network analysis trustconsensus based approach to group decision-making problems with interval-valued fuzzy reciprocal preference relations, Knowledge-Based Systems 59 (2014), 97–107.

49.

Xie

and Beni

, A validity measure for fuzzy clustering, IEEE Transactions on Pattern Analysis and Machine Intelligence 13(8) (1991), 841–847.

50.

Yager

and Kacprzyk

J.E.

, The OrderedWeightedAveraging Operators. Springer Science & Business Media (2012).

51.

Yuan

, Soh

, Yang

and Quek

, Learning overlapping community-based networks, IEEE Transactions on Signal and Information Processing over Networks 5(4) (2019), 684–697.

52.

Zadeh

, Fuzzy sets, Information and Control 8 (1975), 338–353.

53.

Zhao

, Zheng

, Li

, Sun

and Chang

, A comparative study on community detection methods in complex networks, Journal of Intelligent and Fuzzy Systems 35(1) (2018), 1077–1086.

54.

Zhong

, Ma

, Ong

, Zhu

and Zhang

, Computational intelligence in optical remote sensing image processing, Applied Soft Computing 64 (2018), 75–93.

Fuzzy Measures: A solution to deal with community detection problems for networks with additional information

Abstract

Keywords

1 Introduction

3 Fuzzy measures based on relations

5.1 Benchmark graphs

Table 1 Benchmark Parameters Label α β 1 0.45 0.016 2 0.4 0,033 3 0.35 0.05 4 0.325 0.058 5 0.3 0.066 6 0.275 0.075 7 0.25 0.083 8 0.225 0.091 9 0.2 0.1

5.2.2 Benchmark model. Case 2

5.2.3 Benchmark model. Case 3

5.2.4 Benchmark model. Case 4

6 Conclusions and further research

Acknowledgments

References

Table 1
Benchmark Parameters

Label α β

1 0.45 0.016

2 0.4 0,033

3 0.35 0.05

4 0.325 0.058

5 0.3 0.066

6 0.275 0.075

7 0.25 0.083

8 0.225 0.091

9 0.2 0.1