Kuang Zhou

Arnaud Martin
email: arnaud.martin@univ-rennes1.fr

Quan Pan

Zhun-Ga Liu

Median evidential c-means algorithm and its application to community detection

Keywords: Credal partition, Belief function theory, Median clustering, Community detection, Imprecise communities

Median clustering is of great value for partitioning relational data. In this paper, a new prototypebased clustering method, called Median Evidential C-Means (MECM), which is an extension of median c-means and median fuzzy c-means on the theoretical framework of belief functions is proposed. The median variant relaxes the restriction of a metric space embedding for the objects but constrains the prototypes to be in the original data set. Due to these properties, MECM could be applied to graph clustering problems. A community detection scheme for social networks based on MECM is investigated and the obtained credal partitions of graphs, which are more refined than crisp and fuzzy ones, enable us to have a better understanding of the graph structures. An initial prototype-selection scheme based on evidential semi-centrality is presented to avoid local premature convergence and an evidential modularity function is defined to choose the optimal number of communities. Finally, experiments in synthetic and real data sets illustrate the performance of MECM and show its difference to other methods.

Introduction

Cluster analysis or clustering is the task of partitioning a set of n objects X = {x 1 , x 2 , • • • , x n } into c small groups Ω = {ω 1 , ω 2 , • • • , ω c } in such a way that objects in the same group (called a cluster) are more similar (in some sense or another, like characteristics or behavior) to each other than to those in other groups. The clustering can be used in many fields such as privacy preserving [START_REF] Islam | Privacy preserving data mining: a noise addition framework using a novel clustering technique[END_REF] , information retrieval [START_REF] Bordogna | A quality driven hierarchical data divisive soft clustering for information retrieval[END_REF], text analysis [START_REF] Zhang | Text clustering using frequent itemsets[END_REF], etc. It can also be used as the first step of classification problems to identify the distribution of the training set [START_REF] Yang | A kernel fuzzy c-means clustering-based fuzzy support vector machine algorithm for classification problems with outliers or noises[END_REF]. Among the existing approaches to clustering, the objective function-driven or prototype-based clustering such as cmeans and Gaussian mixture modeling is one of the most widely applied paradigms in statistical pattern recognition. These methods are based on a fundamentally very simple, but nevertheless very effective idea, namely to describe the data under consideration by a set of prototypes. They capture the characteristics of the data distribution (like location, size, and shape), and classify the data set based on the similarities (or dissimilarities) of the objects to their prototypes [START_REF] Borgelt | Prototype-based classification and clustering[END_REF].

Generally, a c-partition of n objects in X is a set of n×c values {u ij } arrayed as an n×c matrix U . Each element u ij is the membership of x i to cluster j. The classical C-Means (CM) method aims to partition n observations into c groups in which each observation belongs to the class with the nearest mean, serving as a prototype of the cluster. It results in u ij is either 0 or 1 depending whether object i is grouped into cluster j, and thus each data point is assigned to a single cluster (hard partitions). Fuzzy C-Means (FCM), proposed by Dunn [START_REF] Dunn | A fuzzy relative of the isodata process and its use in detecting compact well-separated clusters[END_REF] and later improved by Bezdek [START_REF] Bezdek | Pattern recognition with fuzzy objective function algorithms[END_REF], is an extension of c-means where each data point can be a member of multiple clusters with membership values (fuzzy partitions) [START_REF] Jain | Data clustering: 50 years beyond k-means[END_REF].

Belief functions have already been used to express partial information about data both in supervised and unsupervised learning [START_REF] Masson | ECM: An evidential version of the fuzzy c-means algorithm[END_REF][START_REF] Tabassian | Combining complementary information sources in the Dempster-Shafer framework for solving classification problems with imperfect labels[END_REF]. Recently, Masson and Denoeux [START_REF] Masson | ECM: An evidential version of the fuzzy c-means algorithm[END_REF] proposed the application of evidential c-means (ECM) to get credal partitions [START_REF] Denoeux | EVCLUS: evidential clustering of proximity data[END_REF] for object data. The credal partition is a general extension of the crisp (hard) and fuzzy ones and it allows the object not only to belong to single clusters, but also to belong to any subsets of Ω by allocating a mass of belief for each object in X over the power set 2 Ω . The additional flexibility brought by the power set provides more refined partitioning results than those by the other techniques allowing us to gain a deeper insight into the data [START_REF] Masson | ECM: An evidential version of the fuzzy c-means algorithm[END_REF].

All of these aforementioned partition approaches are prototype-based. In CM, FCM and ECM, the prototypes of clusters are the geometric centers of included data points in the corresponding groups. However, this may be inappropriate as it is the case in community detection problems for social networks, where the prototype (center) of one group is likely to be one of the persons (i.e. nodes in the graph) playing the leader role in the community. That is to say, one of the points in the group is better to be selected as a prototype, rather than the center of all the points. Thus we should set some constraints for the prototypes, for example, let them be data objects. Actually this is the basic principle of median clustering methods [START_REF] Geweniger | Median fuzzy c-means for clustering dissimilarity data[END_REF]. These restrictions on prototypes can relax the assumption of a metric space embedding for the objects to be clustered [START_REF] Geweniger | Median fuzzy c-means for clustering dissimilarity data[END_REF][START_REF] Hammer | Relational neural gas[END_REF], and only similarity or dissimilarity between data objects is required. There are some clustering methods for relational data, such as Relational FCM (RFCM) [START_REF] Hathaway | Relational duals of the c-means clustering algorithms[END_REF] and Relational ECM (RECM) [START_REF] Masson | RECM: Relational evidential c-means algorithm[END_REF], but an underlying metric is assumed for the given dissimilarities between objects. However, in median clustering this restriction is dropped [START_REF] Geweniger | Median fuzzy c-means for clustering dissimilarity data[END_REF]. Cottrell et al. [START_REF] Cottrell | Batch and median neural gas[END_REF] proposed Median C-Means clustering method (MCM) which is a variant of the classic c-means and proved the convergence of the algorithm. Geweniger et al. [START_REF] Geweniger | Median fuzzy c-means for clustering dissimilarity data[END_REF] combined MCM with the fuzzy c-means approach and investigated the behavior of the resulted Median Fuzzy C-means (MFCM) algorithm.

Community detection, which can extract specific structures from complex networks, has attracted considerable attention crossing many areas from physics, biology, and economics to sociology. Recently, significant progress has been achieved in this research field and several popular algorithms for community detection have been presented. One of the most popular type of classical methods partitions networks by optimizing some criteria. Newman and Girvan [START_REF] Newman | Finding and evaluating community structure in networks[END_REF] proposed a network modularity measure (usually denoted by Q) and several algorithms that try to maximize Q have been designed [START_REF] Blondel | Fast unfolding of communities in large networks[END_REF][START_REF] Clauset | Finding community structure in very large networks[END_REF][START_REF] Duch | Community detection in complex networks using extremal optimization[END_REF][START_REF] Tasgin | Community detection in complex networks using genetic algorithms[END_REF]. But recent researches have found that the modularity based algorithms could not detect communities smaller than a certain size. This problem is famously known as the resolution limit [START_REF] Fortunato | Resolution limit in community detection[END_REF]. The single optimization criteria i.e. modularity may not be adequate to represent the structures in complex networks, thus Amiri et al. [START_REF] Amiri | Community detection in complex networks: Multi-objective enhanced firefly algorithm[END_REF] suggested a new community detection process as a multi-objective optimization problem. Another family of approaches considers hierarchical clustering techniques. It merges or splits clusters according to a topological measure of similarity between the nodes and tries to build a hierarchical tree of partitions [START_REF] Lancichinetti | Detecting the overlapping and hierarchical community structure in complex networks[END_REF][START_REF] Sales-Pardo | Extracting the hierarchical organization of complex systems[END_REF][START_REF] Yang | Hierarchical community detection with applications to real-world network analysis[END_REF]. Also there are some ways, such as spectral methods [START_REF] Smyth | A spectral clustering approach to finding communities in graphs[END_REF] and signal process method [START_REF] Hu | Community detection by signaling on complex networks[END_REF][START_REF] Jiang | An efficient community detection method based on rank centrality[END_REF], to map topological relationship of nodes on networks into geometrical structures of vectors in n-dimensional Euclidian space, where classical clustering methods like CM, FCM and ECM could be evoked. However, there must be some loss of accuracy after the mapping process.

As mentioned before, for community detection, the prototypes should be some nodes in the graph.

Besides, usually only dissimilarities between nodes are known to us. Due to the application of the relaxation on the data objects and the constraints on the prototypes, the median clustering could be applied to the community detection problem in social networks.

In this paper, we extend the median clustering methods in the framework of belief functions theory and put forward the Median Evidential C-Means (MECM) algorithm. Moreover, a community detection scheme based on MECM is also presented. Here, we emphasize two key points different from those earlier studies. Firstly, the proposed approach could provide credal partitions for data set with only known dissimilarities. The dissimilarity measure could be neither symmetric nor fulfilling any metric requirements. It is only required to be of intuitive meaning. Thus it expands application scope of credal partitions. Secondly, some practical issues about how to apply the method into community detection problems such as how to determine the initial prototypes and the optimum community number in the sense of credal partitions are discussed. This makes the approach appropriate for graph partitions and gives us a better understanding of the analysed networks, especially for the uncertain and imprecise structures.

The rest of this paper is organized as follows: Section 2 recalls the necessary background related to this paper. In Section 3, the median c-means algorithm is presented and in section 4, we show how the proposed method could be applied in the community detection problem. In order to show the effectiveness of our approach, in section 5 we test our algorithm on artificial and real-world data sets and make comparisons with different methods. The final section makes the conclusions.

Background

Theory of belief functions

Let Ω = {ω 1 , ω 2 , . . . , ω c } be the finite domain of X, called the discernment frame. The mass function is defined on the power set 2 Ω = {A : A ⊆ Ω}.

Definition 1. The function

m : 2 Ω → [0, 1] is said to be the Basic Belief Assignment (bba) on 2 Ω , if it satisfies: ∑ A⊆Ω m(A) = 1. ( 1
)
Every A ∈ 2 Ω such that m(A) > 0 is called a focal element.
The credibility and plausibility functions are defined in Eq. (2) and Eq. [START_REF] Bezdek | Pattern recognition with fuzzy objective function algorithms[END_REF].

Bel(A) = ∑ B⊆A,B̸ =∅ m(B), ∀A ⊆ Ω, (2)
P l(A) = ∑ B∩A̸ =∅ m(B), ∀A ⊆ Ω. (3)
Each quantity Bel(A) measures the total support given to A, while P l(A) can be interpreted as the degree to which the evidence fails to support the complement of A. The function pl : Ω → [0, 1] such that pl(ω i ) = P l({ω i }) (ω i ∈ Ω) is called the contour function associated with m. A belief function on the credal level can be transformed into a probability function by Smets method. In this algorithm, each mass of belief m(A) is equally distributed among the elements of A [START_REF] Smets | Decision making in the TBM: the necessity of the pignistic transformation[END_REF]. This leads to the concept of pignistic probability, BetP , defined by

BetP (ω i ) = ∑ ωi∈A⊆Ω m(A) |A|(1 -m(∅)) , ( 4
)
where |A| is the number of elements of Ω in A.

Pignistic probabilities, which play the same role as fuzzy membership, can easily help us make a decision. In fact, belief functions provide us many decision-making techniques not only in the form of probability measures. For instance, a pessimistic decision can be made by maximizing the credibility function, while maximizing the plausibility function could provide an optimistic one [START_REF] Martin | Decision support with belief functions theory for seabed characterization[END_REF]. Another criterion [START_REF] Martin | Decision support with belief functions theory for seabed characterization[END_REF] considers the plausibility functions and consists in attributing the class

A j for object i if A j = arg max X⊆Ω {m b i (X)P l i (X)}, (5)
where

m b i (X) = K b i λ X ( 1 |X| r ) . ( 6
)
In Eq. ( 5) m b i (X) is a weight on P l i (X), and r is a parameter in [0, 1] allowing a decision from a simple class (r = 1) until the total ignorance Ω (r = 0). The value λ X allows the integration of the lack of knowledge on one of the focal sets X ⊆ Ω, and it can be set to be 1 simply. Coefficient

K b
i is the normalization factor to constrain the mass to be in the closed world:

K b i = 1 1 -m i (∅) . ( 7
)

Median c-means and median fuzzy c-means

Median c-means is a variant of the traditional c-means method [START_REF] Cottrell | Batch and median neural gas[END_REF][START_REF] Geweniger | Median fuzzy c-means for clustering dissimilarity data[END_REF]. We assume that n

(p-dimensional) data objects x i = {x i1 , x i2 , • • • , x ip } (i = 1, 2, • • • , n) are given. The object set is denoted by X = {x 1 , x 2 , • • • , x n }.
The objective function of MCM is similar to that in CM:

J MCM = c ∑ j=1 n ∑ i=1 u ij d 2 ij , ( 8
)
where c is the number of clusters. As MCM is based on crisp partitions, u ij is either 0 or 1 depending whether x i is in cluster j. The value d ij is the dissimilarity between x i and the prototype vector

v j of cluster j (i = 1, 2, • • • , n, j = 1, 2, • • • , c
), which is not assumed to be fulfilling any metric properties but should reflect the common sense of dissimilarity. Due to these weak assumptions, data object x i itself may be a general choice and it does not have to live in a metric space [START_REF] Geweniger | Median fuzzy c-means for clustering dissimilarity data[END_REF].

The main difference between MCM and CM is that the prototypes of MCM are restricted to the data objects.

Median fuzzy c-means (MFCM) merges MCM and the standard fuzzy c-means (FCM). As in MCM, it requires the knowledge of the dissimilarity between data objects, and the prototypes are restricted to the objects themselves [START_REF] Geweniger | Median fuzzy c-means for clustering dissimilarity data[END_REF]. MFCM also performs a two-step iteration scheme to minimize the cost function

J MFCM = c ∑ j=1 n ∑ i=1 u β ij d 2 ij , (9)
subject to the constrains

c ∑ k=1 u ik = 1, ∀i ∈ {1, 2, • • • , n}, (10)
and

n ∑ i=1 u ik > 0, ∀k ∈ {1, 2, • • • , c}, (11)
where each number u ik ∈ [0, 1] is interpreted as a degree of membership of object i to cluster k, and β > 1 is a weighting exponent that controls the fuzziness of the partition. Again, MFCM is preformed by alternating update steps as for MCM:

• Assignment update:

u ij = d -2/(β-1) ij ∑ c k=1 d -2/(β-1) ik . ( 12
)
• Prototype update: the new prototype of cluster j is set to be v j = x l * with

x l * = arg min {vj :vj =x l (∈X)} n ∑ i=1 u β ij d 2 ij . ( 13
)

Evidential c-means

Evidential c-means [START_REF] Masson | ECM: An evidential version of the fuzzy c-means algorithm[END_REF] is a direct generalization of FCM in the framework of belief functions, and it is based on the credal partition first proposed by Denoeux and Masson [START_REF] Denoeux | EVCLUS: evidential clustering of proximity data[END_REF]. The credal partition takes advantage of imprecise (meta) classes [START_REF] Liu | Evidential classifier for imprecise data based on belief functions[END_REF] to express partial knowledge of class memberships. The principle is different from another belief clustering method put forward by Schubert [START_REF] Schubert | Clustering belief functions based on attracting and conflicting metalevel evidence using potts spin mean field theory[END_REF], in which conflict between evidence is utilised to cluster the belief functions related to multiple events. In ECM, the evidential membership of an object

x i = {x i1 , x i2 , • • • , x ip } is represented by a bba m i = (m i (A j ) : A j ⊆ Ω) over the given frame of discernment Ω = {ω 1 , ω 2 , • • • , ω c }.
The optimal credal partition is obtained by minimizing the following objective function:

J ECM = n ∑ i=1 ∑ Aj ⊆Ω,Aj ̸ =∅ |A j | α m i (A j ) β d 2 ij + n ∑ i=1 δ 2 m i (∅) β (14) constrained on ∑ Aj ⊆Ω,Aj ̸ =∅ m i (A j ) + m i (∅) = 1, (15)
where m i (A j ) m ij is the bba of x i given to the nonempty set A j , while m i (∅) m i∅ is the bba of x i assigned to the emptyset, and |•| is the cardinality of the set. Parameter α is a tuning parameter allowing to control the degree of penalization for subsets with high cardinality, parameter β is a weighting exponent and δ is an adjustable threshold for detecting the outliers. It is noted that for credal partitions, j is not from 1 to c as before, but ranges in [0, f ] with f = 2 c . Here d ij denotes the Euclidean distance between x i and the barycenter (i.e. prototype, denoted by v j ) associated with A j :

d 2 ij = ∥x i -v j ∥ 2 , ( 16
)
where v j is defined mathematically by

v j = 1 |A j | c ∑ k=1 s kj v k , with s kj =    1 if ω k ∈ A k 0 else . ( 17
)
The notation ∥ • ∥ denotes the Euclidean norm of a vector, and v k is the geometrical center of all the points in cluster k. The update for ECM is given by the following two alternating steps and the update formulas can been obtained by Lagrange multipliers method.

• Assignment update:

m ij = |A j | -α/(β-1) d -2/(β-1) ij ∑ A k ̸ =∅ |A k | -α/(β-1) d -2/(β-1) ik + δ -2/(β-1) , ∀i = 1, 2 • • • , n, ∀j/A j ⊆ Ω, A j ̸ = ∅ (18) m i∅ = 1 - ∑ Aj ̸ =∅ m ij , ∀i = 1, 2, • • • , n. ( 19
)
• Prototype update: The prototypes (centers) of the classes are given by the rows of the matrix v c×p , which is the solution of the following linear system:

HV = B, ( 20
)
where H is a matrix of size (c × c) given by

H lk = ∑ i ∑ Aj {ω k ,ω l } |A j | α-2 m β ij , k, l = 1, 2, • • • , c, (21)
and B is a matrix of size (c × p) defined by

B lq = n ∑ i=1 x iq ∑ Aj ∋ω l |A j | α-1 m β ij , l = 1, 2, • • • , c, q = 1, 2, • • • , p. ( 22
)

Some concepts for social networks

In this work we will investigate how the proposed clustering algorithm could be applied to community detection problems in social networks. In this section some concepts related to social networks will be recalled.

Centrality and dissimilarity

The problem of assigning centrality values to nodes in graphs has been widely investigated as it is important for identifying influential nodes [START_REF] Zhang | Identifying influential nodes in complex networks with community structure[END_REF]. Gao et al. [START_REF] Gao | A modified evidential methodology of identifying influential nodes in weighted networks[END_REF] put forward Evidential Semi-local Centrality (ESC) and pointed out that it is more reasonable than the existing centrality measures such as Degree Centrality (DC), Betweenness Centrality (BC) and Closeness Centrality (CC). In the application of ESC, the degree and strength of each node are first expressed by bbas, and then the fused importance is calculated using the combination rule in belief function theory.

The higher the ESC value is, the more important the node is. The detail computation process of ESC can be found in [START_REF] Gao | A modified evidential methodology of identifying influential nodes in weighted networks[END_REF].

The similarity or dissimilarity index signifies to what extent the proximity between two vertices of a graph is. The dissimilarity measure considered in this paper is the one put forward by Zhou [START_REF] Zhou | Distance, dissimilarity index, and network community structure[END_REF].

This index relates a network to a discrete-time Markov chain and utilises the mean first-passage time to express the distance between two nodes. One can refer to [START_REF] Zhou | Distance, dissimilarity index, and network community structure[END_REF] for more details.

Modularity

Recently, many criteria were proposed for evaluating the partition of a network. A widely used measure called modularity, or Q was presented by Newman and Girvan [START_REF] Newman | Finding and evaluating community structure in networks[END_REF]. Given a hard partition with c groups (ω 1 , ω 2 , • • • , ω c ) U = (u ik ) n×c , where u ik is one if vertex i belongs to the k th community, 0 otherwise, and let the c crisp subsets of vertices be {V 1 , V 2 , • • • , V c }, then the modularity can be defined as [START_REF] Fortunato | Community detection in graphs[END_REF]:

Q h = 1 ∥W ∥ c ∑ k=1 ∑ i,j∈V k ( w ij - k i k j ∥W ∥ ) , ( 23
)
where

∥W ∥ = ∑ n i,j=1 w ij , k i = ∑ n j=1 w ij . The node subsets {V k , k = 1, 2, • • • , c}
are determined by the hard partition U n×c , but the role of U is somewhat obscured by this form of modularity function. To reveal the role played by the partition U explicitly, Havens et al. [START_REF] Havens | A soft modularity function for detecting fuzzy communities in social networks[END_REF] rewrote the equations in the form of

U . Let k = (k 1 , k 2 , • • • , k n ) T , B = W -k T k/ ∥W ∥, then Q h = 1 ∥W ∥ c ∑ k=1 n ∑ i,j=1 ( w ij - k i k j ∥W ∥ ) u ik u jk = 1 ∥W ∥ c ∑ k=1 u k Bu T k = trace ( U T BU ) /∥W ∥, (24)
where

u k = (u 1k , u 2k , • • • , u nk ) T .
Havens et al. [START_REF] Havens | A soft modularity function for detecting fuzzy communities in social networks[END_REF] pointed out that an advantage of Eq. ( 24) is that it is well defined for any partition of the nodes not just crisp ones. The fuzzy modularity of U was derived as

Q f = trace ( U T BU ) /∥W ∥, ( 25
)
where U is the membership matrix and u ik represents the membership of community k for node i.

If u ik is restricted in [0, 1], the fuzzy partition degrades to the hard one, and so Q f equals to Q h at this time.

Median Evidential C-Means (MECM) approach

We introduce here median evidential c-means in order to take advantages of both median clustering and credal partitions. Like all the prototype-based clustering methods, for MECM, an objective function should first be found to provide an immediate measure of the quality of clustering results. Our goal then can be characterized as the optimization of the objective function to get the best credal partition.

The objective function of MECM

To group n objects in

X = {x 1 , x 2 , • • • , x n } into c clusters ω 1 , ω 2 , • • • , ω c , the credal partition M = {m 1 , m 2 , • • • , m n } defined on Ω = {ω 1 , ω 2 , • • • , ω c } is used to represent the class membership
of the objects, as in [START_REF] Denoeux | EVCLUS: evidential clustering of proximity data[END_REF][START_REF] Masson | ECM: An evidential version of the fuzzy c-means algorithm[END_REF]. The quantities m ij = m i (A j ) (A j ̸ = ∅, A j ⊆ Ω) are determined by the dissimilarity between object x i and focal set A j which has to be defined first.

Let the prototype set of specific (singleton) cluster be

V = {v 1 , v 2 , • • • , v c },
where v i is the prototype vector of cluster ω i (i = 1, 2, • • • , c) and it must be one of the n objects.

If |A j | = 1, i.e.,
A j is associated with one of the singleton clusters in Ω (suppose to be ω j with prototype vector v j ), then the dissimilarity between x i and A j is defined by

d 2 ij = d 2 (x i , v j ), (26)
where d(x i , x j ) represents the known dissimilarity between object x i and x j . When

|A j | > 1,
it represents an imprecise (meta) cluster. If object x i is to be partitioned into a meta cluster, two conditions should be satisfied. One is the dissimilarity values between x i and the included singleton classes' prototypes are similar. The other is the object should be close to the prototypes of all these specific clusters. The former measures the degree of uncertainty, while the latter is to avoid the pitfall of partitioning two data objects irrelevant to any included specific clusters into the corresponding imprecise classes. Let the prototype vector of the imprecise cluster associated with A j be v j , then the dissimilarity between x i and A j can be defined as:

d 2 ij = γ 1 |Aj | ∑ ω k ∈Aj d 2 (x i , v k ) + ρ ij min{d(x i , v k ) : ω k ∈ A j } γ + 1 , ( 27
)
with

ρ ij = ∑ ωx,ωy∈Aj √ (d (x i , v x ) -d(x i , v y )) 2 η ∑ ωx,ωy∈Aj d(v x , v y ) . ( 28
)
In Eq. ( 27) γ weights the contribution of the dissimilarity of the objects from the consisted specific clusters and it can be tuned according to the applications. If γ = 0, the imprecise clusters only consider our uncertainty. Discounting factor ρ ij reflects the degree of uncertainty. If ρ ij = 0, it means that all the dissimilarity values between x i and the included specific classes in A j are equal, and we are absolutely uncertain about which cluster object x i is actually in. Parameter η (∈ [0, 1]) can be tuned to control of the discounting degree. In credal partitions, we can distinguish between "equal evidence" (uncertainty) and "ignorance". The ignorance reflects the indistinguishability among the clusters. In fact, imprecise classes take both uncertainty and ignorance into consideration, and we can balance the two types of imprecise information by adjusting γ. Therefore, the dissimilarity between x i and A j (A j ̸ = ∅, A j ⊆ Ω), d ij , can be calculated by

d 2 ij =      d 2 (x i , v j ) |A j | = 1, γ 1 |A j | ∑ ω k ∈A j d 2 (xi,v k )+ρij min{d(xi,v k ):ω k ∈Aj } γ+1 |A j | > 1 . ( 29
)
Like ECM, we propose to look for the credal partition

M = {m 1 , m 2 , • • • , m n } ∈ R n×2 c and the prototype set V = {v 1 , v 2 , • • • , v c } of specific (singleton)
clusters by minimizing the objective function:

J MECM (M , V ) = n ∑ i=1 ∑ Aj ⊆Ω,Aj ̸ =∅ |A j | α m β ij d 2 ij + n ∑ i=1 δ 2 m β i∅ , ( 30
) constrained on ∑ Aj ⊆Ω,Aj ̸ =∅ m ij + m i∅ = 1, (31)
where m ij m i (A j ) is the bba of n i given to the nonempty set A j , m i∅ m i (∅) is the bba of n i assigned to the empty set, and d ij is the dissimilarity between x i and focal set A j . Parameters α, β, δ are adjustable with the same meanings as those in ECM. Note that J MECM depends on the credal partition M and the set V of all prototypes.

The optimization

To minimize J MECM , an optimization scheme via an Expectation-Maximization (EM) algorithm as in MCM [START_REF] Cottrell | Batch and median neural gas[END_REF] and MFCM [START_REF] Geweniger | Median fuzzy c-means for clustering dissimilarity data[END_REF] can be designed, and the alternate update steps are as follows:

Step 1. Credal partition (M ) update.

• ∀A j ⊆ Ω, A j ̸ = ∅, m ij = |A j | -α/(β-1) d -2/(β-1) ij ∑ A k ̸ =∅ |A k | -α/(β-1) d -2/(β-1) ik + δ -2/(β-1)
(32)

• if A j = ∅, m i∅ = 1 - ∑ Aj ̸ =∅ m ij ( 33
)
Step 2. Prototype (V ) update.

The prototype v i of a specific (singleton) cluster

ω i (i = 1, 2, • • • , c
) can be updated first and then the dissimilarity between the object and the prototype of each imprecise (meta) clusters associated with subset A j ⊆ Ω can be obtained by Eq. ( 29). For singleton clusters

ω k (k = 1, 2, • • • , c), the corresponding new prototypes v k (k = 1, 2, • • • , c
) are set to be sample x l orderly, with

x l = arg min v ′ k    L(v ′ k ) n ∑ i=1 ∑ ω k ∈Aj |A j | α m β ij d 2 ij (v ′ k ), v ′ k ∈ {x 1 , x 2 , • • • , x n }    , ( 34
)
The dissimilarity between x i and A j , d

2 ij , is a function of v ′ k
, which is the prototype of ω k (∈ A j ), and it should be one of the n objects in

X = {x 1 , x 2 , • • • , x n }.
The bbas of the objects' class membership are updated identically to ECM [START_REF] Masson | ECM: An evidential version of the fuzzy c-means algorithm[END_REF], but it is worth noting that d ij has different meanings and less constraints as explained before. For the prototype updating process the fact that the prototypes are assumed to be one of the data objects is taken into account. Therefore, when the credal partition matrix M is fixed, the new prototypes of the clusters can be obtained in a simpler manner than in the case of ECM application. The MECM algorithm is summarized as Algorithm 1.

The convergence of MECM algorithm can be proved in the following lemma, similar to the proof of median neural gas [START_REF] Cottrell | Batch and median neural gas[END_REF] and MFCM [START_REF] Geweniger | Median fuzzy c-means for clustering dissimilarity data[END_REF].

Lemma 1. The MECM algorithm (Algorithm 1) converges in a finite number of steps.

Proof: Suppose θ (t) = (M t , V t ) and θ (t+1) = (M t+1 , V t+1 ) are the parameters from two successive iterations of MECM. We will first prove that

J M ECM (θ (t) ) ≥ J M ECM (θ (t+1) ), (35)
Algorithm 1 : Median evidential c-means algorithm

Input dissimilarity matrix D [d(x i , x j )] n×n for the n objects {x 1 , x 2 , • • • , x n } Parameters c: number clusters 1 < c < n α:
weighing exponent for cardinality β > 1: weighting exponent δ > 0: dissimilarity between any object to the emptyset γ > 0: weight of dissimilarity between data and prototype vectors η ∈ [0, 1]: control of the discounting degree

Initialization

Choose randomly c initial cluster prototypes from the objects

Loop t ← 0 Repeat (1). t ← t + 1 (2)
. Compute M t using Eq. ( 32), Eq. ( 33) and V t-1 [START_REF] Bezdek | Pattern recognition with fuzzy objective function algorithms[END_REF]. Compute the new prototype set V t using Eq. ( 34) Until the prototypes remain unchanged which shows MECM always monotonically decreases the objective function. Let

J (t) M ECM = n ∑ i=1 ∑ Aj ⊆Ω,Aj ̸ =∅ |A j | α (m (t) ij ) β (d (t) ij ) 2 + n ∑ i=1 δ 2 (m (t) i∅ ) β ∑ i ∑ j f 1 (M t )f 2 (V t ) + ∑ i f 3 (M t ), (36)
where

f 1 (M t ) = |A j | α (m (t) ij ) β , f 2 (V t ) = (d (t) ij ) 2 , and f 3 (M t ) = δ 2 (m (t) i∅ ) β
. M t+1 is then obtained by maximizing the right hand side of the equation above. Thus,

J (t) M ECM ≥ ∑ i ∑ j f 1 (M t+1 )f 2 (V t ) + ∑ i f 3 (M t+1 ) ( 37
)
≥ ∑ i ∑ j f 1 (M t+1 )f 2 (V t+1 ) + ∑ i f 3 (M t+1 ) (38) = J (t+1) M ECM . ( 39
)
This inequality (37) comes from the fact M t+1 is determined by differentiating of the respective Lagrangian of the cost function with respect to M t . To get Eq. [START_REF] Schubert | Clustering belief functions based on attracting and conflicting metalevel evidence using potts spin mean field theory[END_REF], we could use the fact that

every prototype v k (k = 1, 2, • • • , c) in V t+1 is orderly chosen explicitly to be arg min v ′ k    L(v ′ k ) n ∑ i=1 ∑ ω k ∈Aj |A j | α m β ij d 2 ij (v ′ k ), v ′ k ∈ {x 1 , x 2 , • • • , x n }    ,
and thus this formula evaluated at V t+1 must be equal to or less than the same formula evaluated at V t .

Hence MECM causes the objective function to converge monotonically. Moreover, the bba M is a function of the prototypes V and for given V the assignment M is unique. Because MECM assumes that the prototypes are original object data in X, so there is a finite number of different prototype vectors V and so is the number of corresponding credal partitions M . Consequently we can get the conclusion that the MECM algorithm converges in a finite number of steps.

Remark 1. Although the objective function of MECM takes the same form as that in ECM [START_REF] Masson | ECM: An evidential version of the fuzzy c-means algorithm[END_REF], we should note that in MECM, it is no longer assumed that there is an underlying Euclidean distance. Thus the dissimilarity measure d ij has few restrictions such as the triangle inequality or the symmetry. This freedom distinguishes the MECM from ECM and RECM, and it leads to the constraint for the prototypes to be data objects themselves. The distinct difference in the process of minimization between MECM and ECM lies in the prototype-update step. The purpose of updating the prototypes is to make sure that the cost function would decrease. In ECM the Lagrange multiplier optimization is evoked directly while in MECM a search method is applied.

As a result, the objective function may decline more quickly in ECM as the optimization process has few constraints. However, when the centers of clusters in the data set are more likely to be the data object, MECM may converge with few steps.

Remark 2. Although both MECM and MFCM can be applied to the same type of data set, they are very different. This is due to the fact that they are founded on different models of partitioning. MFCM provides fuzzy partition. In contrast, MECM gives credal partitions. We emphasize that MECM is in line with MCM and MFCM: each class is represented by a prototype which is restricted to the data objects and the dissimilarities are not assumed to be fulfilling any metric properties. MECM is an extension of MCM and MFCM in the framework of belief functions.

The parameters of the algorithm

As in ECM, before running MECM, the values of the parameters have to be set. Parameters α, β and δ have the same meanings as those in ECM, and γ weighs the contribution of uncertainty to the dissimilarity between nodes and imprecise clusters. The value β can be set to be β = 2 in all experiments for which it is a usual choice. The parameter α aims to penalize the subsets with high cardinality and control the amount of points assigned to imprecise clusters in both ECM and MECM. As the measures for the dissimilarity between nodes and meta classes are different, thus different values of α should be taken even for the same data set. But both in ECM and MECM, the higher α is, the less mass belief is assigned to the meta clusters and the less imprecise will be the resulting partition. However, the decrease of imprecision may result in high risk of errors. For instance, in the case of hard partitions, the clustering results are completely precise but there is much more intendancy to partition an object to an unrelated group. As suggested in [START_REF] Masson | ECM: An evidential version of the fuzzy c-means algorithm[END_REF], a value can be used as a starting default one but it can be modified according to what is expected from the user. The choice δ is more difficult and is strongly data dependent [START_REF] Masson | ECM: An evidential version of the fuzzy c-means algorithm[END_REF].

For determining the number of clusters, the validity index of a credal partition defined by Masson and Denoeux [START_REF] Masson | ECM: An evidential version of the fuzzy c-means algorithm[END_REF] could be utilised:

N * (c) 1 n log 2 (c) × n ∑ i=1   ∑ A∈2 Ω \∅ m i (A) log 2 |A| + m i (∅) log 2 (c)   , ( 40
)
where 0 ≤ N * (c) ≤ 1. This index has to be minimized to get the optimal number of clusters. When MECM is applied to community detection, a different index is defined to determine the number of communities. We will describe it in the next section.

Application and evaluation issues

In this section, we will discuss how to apply MECM to community detection problems in social networks and how to evaluate credal partitions.

Evidential modular function

Assume the obtained credal partition of the graph is

M = [m 1 , m 2 , • • • , m n ] T ,
where

m i = (m i1 , m i2 , • • • , m ic ) T .
Similarly to the fuzzy modularity by Havens et al. [START_REF] Havens | A soft modularity function for detecting fuzzy communities in social networks[END_REF], here we introduce an evidential modularity [START_REF] Zhou | Evidential communities for complex networks[END_REF]:

Q e = 1 ∥W ∥ c ∑ k=1 n ∑ i,j=1 ( w ij - k i k j ∥W ∥ ) pl ik pl jk , ( 41
)
where

pl i = (pl i1 , pl i2 , • • • , pl ic )
T is the contour function associated with m i , which describes the upper value of our belief to the proposition that the i th node belongs to the k th community.

Let P L = (pl ik ) n×c , then Eq. ( 41) can be rewritten as:

Q e = trace(P L T B P L) ∥W ∥ . ( 42
)
Q e is a directly extension of the crisp and fuzzy modularity functions in Eq. ( 24). When the credal partition degrades into the hard and fuzzy ones, Q e is equal to Q h and Q f respectively.

The initial prototypes for communities

Generally speaking, the person who is the center in the community in a social network has the following characteristics: he has relation with all the members of the group and their relationship is stronger than usual; he may directly contact with other persons who also play an important role in their own community. For instance, in Twitter network, all the members in the community of the fans of Real Madrid football Club (RMC) are following the official account of the team, and RMC must be the center of this community. RMC follows the famous football player in the club, who is sure to be the center of the community of his fans. In fact, RMC has 10382777 followers and 30 followings (the data on March 16, 2014). Most of the followings have more than 500000 followers. Therefore, the centers of the community can be set to the ones not only with high degree and strength, but also with neighbours who also have high degree and strength. Thanks to the theory of belief functions, the evidential semi-local centrality ranks the nodes considering all these measures. Therefore the initial c prototypes of each community can be set to the nodes with largest ESC values.

Note that there is usually more than one center in one community. Take Twitter network for example again, the fans of RMC who follow the club official account may also pay attention to Cristiano Ronaldo, the most popular player in the team, who could be another center of the community of RMC's fans to a great extent. These two centers (the accounts of the club and Ronaldo) both have large ESC values but they are near to each other. This situation violates the rule which requires the chosen seeds as far away from each other as possible [START_REF] Arthur | k-means++: The advantages of careful seeding[END_REF][START_REF] Jiang | An efficient community detection method based on rank centrality[END_REF].

The dissimilarity between the nodes could be utilised to solve this problem. Suppose the ranking order of the nodes with respect to their ESCs is

n 1 ≥ n 2 ≥ • • • ≥ n n .
In the beginning n 1 is set to be the first prototype as it has the largest ESC, and then node n

2 is considered. If d(n 1 , n 2 )
(the dissimilarity between node 1 and 2) is larger than a threshold µ, it is chosen to be the second prototype. Otherwise, we abandon n 2 and turn to check n 3 . The process continues until all the c prototypes are found. If there are not enough prototypes after checking all the nodes, we should decrease µ moderately and restart the search from n 1 . In this paper we test the approach with the dissimilarity measure proposed in [START_REF] Zhou | Distance, dissimilarity index, and network community structure[END_REF]. Based on our experiments, [0.7, 1] is a better experiential range of the threshold µ. This seed choosing strategy is similar to that in [START_REF] Jiang | An efficient community detection method based on rank centrality[END_REF].

The community detection algorithm based on MECM

The whole community detection algorithm in social networks based on MECM is summarized in Algorithm 2.

Algorithm 2 : Community detection algorithm based on MECM

Input: A, the adjacency matrix; W , the weight matrix (if any); µ, the threshold controlling the dissimilarity between the prototypes; c min , the minimal number of communities; c max , the maximal of communities; the required parameters in original MECM algorithm Initialization: Calculate the dissimilarity matrix of the nodes in the graph. repeat [START_REF] Amiri | Community detection in complex networks: Multi-objective enhanced firefly algorithm[END_REF]. Set the cluster number c in MECM be c = c min .

(2). Choose the initial c prototypes using the strategy proposed in section 4.2.

(3). Run MECM with the corresponding parameters and the initial prototypes got in (2). ( 4). Calculate the evidential modularity using Eq. ( 42).

(5). Let c = c + 1. until c reaches at c max . Output: Choose the number of communities at around which the modular function peaks, and output the corresponding credal partition of the graph.

In the algorithm, c min and c max can be determined based on the original graph. Note that c min ≥ 2. It is an empirical range of the community number of the network. If c is given, we can get a credal partition based on MECM and then the evidential modularity can be derived. As we can see, the modularity is a function of c and it should peak at around the optimal value of c for the given network.

Performance evaluation

The objective of the clustering problem is to partition a similar data pair to the same group. respectively. The Rand index (RI) measures the percentage of correct decisions and it can be defined as

RI = 2(a + b) n(n -1) , ( 44
)
where n is the number of data objects. In fact, precision measures the rate of the first type of errors (FP), recall (R) measures another type (FN), while RI measures both.

For fuzzy and evidential clusterings, objects may be partitioned into multiple clusters with different degrees. In such cases precision would be consequently low [START_REF] Mendes | Evaluating fuzzy clustering for relevance-based information access[END_REF]. Usually the fuzzy and evidential clusters are made crisp before calculating the measures, using for instance the maximum membership criterion [START_REF] Mendes | Evaluating fuzzy clustering for relevance-based information access[END_REF] and pignistic probabilities [START_REF] Masson | ECM: An evidential version of the fuzzy c-means algorithm[END_REF]. Thus in the work presented in this paper, we have hardened the fuzzy and credal clusters by maximizing the corresponding membership and pignistic probabilities and calculate precision, recall and RI for each case.

The introduced imprecise clusters can avoid the risk to group a data into a specific class without strong belief. In other words, a data pair can be clustered into the same specific group only when we are quite confident and thus the misclassification rate will be reduced. However, partitioning too many data into imprecise clusters may cause that many objects are not identified for their precise groups. In order to show the effectiveness of the proposed method in these aspects, we use the evidential precision (EP) and evidential recall (ER):

EP = n er N e , ER = n er N r . ( 45
)
In Eq. ( 45), the notation N e denotes the number of pairs partitioned into the same specific group by evidential clusterings, and n er is the number of relevant instance pairs out of these specifically clustered pairs. The value N r denotes the number of pairs in the same group of the clustering benchmark, and ER is the fraction of specifically retrieved instances (grouped into an identical specific cluster) out of these relevant pairs. When the partition degrades to a crisp one, EP and ER equal to the classical precision and recall measures respectively. EP and ER reflect the accuracy of the credal partition from different points of view, but we could not evaluate the clusterings from one single term. For example, if all the objects are partitioned into imprecise clusters except two relevant data object grouped into a specific class, EP = 1 in this case. But we could not say this is a good partition since it does not provide us with any information of great value. In this case ER ≈ 0. Thus ER could be used to express the efficiency of the method for providing valuable partitions. Certainly we can combine EP and ER like RI to get the evidential rank index (ERI) describing the accuracy:

ERI = 2(a * + b * ) n(n -1) , ( 46
)
where a * (respectively, b * ) is the number of pairs of objects simultaneously clustered to the same specific class (i.e., singleton class, respectively, different classes) by the stand reference partition and the obtained credal one. Note that for evidential clusterings, precision, recall and RI measures are calculated after the corresponding hard partitions are got, while EP, ER and ERI are based on hard credal partitions [START_REF] Masson | ECM: An evidential version of the fuzzy c-means algorithm[END_REF].

Example 1. In order to show the significance of the above performance measures, an example containing only ten objects from two groups is presented here. The three partitions are given in We can see that if we simply partition the nodes in the overlapped area, the risk of misclassification is high in terms of precision. The introduced imprecise cluster ω 12 {ω 1 , ω 2 } could enable us to make soft decisions, as a result the accuracy of the specific partitions is high. However, if too many objects are clustered into imprecise classes, which is the case of partition 3, it is pointless although EP is high. Generally, EP denotes the accuracy of the specific decisions, while ER represents the efficiency of the approach. We remark that the evidential indices degrade to the corresponding classical indices (e.g, evidential precision degrades to precision) when the partition is crisp.

Experiments

In this section a number of experiments are performed on classical data sets in the distance space and on graph data for which only the dissimilarities between nodes are known. The obtained credal partitions are compared with hard and fuzzy ones using the evaluation indices proposed in Section 4.4 to show the merits of MECM.

Overlapped data set

Clustering approaches to detect overlap objects which leads to recent attentions are still inefficiently processed. Due to the introduction of imprecise classes, MECM has the advantage to detect overlapped clusters. In the first example, we will use overlapped data sets to illustrate the behavior of the proposed algorithm.

We start by generating 2 × 100 points uniformly distributed in two overlapped circles with a same radius R = 30 but with different centers. The coordinates of the first circle's center are (0, 0) while the coordinates of the other circle's center are [START_REF] Liu | Evidential classifier for imprecise data based on belief functions[END_REF][START_REF] Liu | Evidential classifier for imprecise data based on belief functions[END_REF]. The data set is displayed in Fig. 2-a. to make more imprecise decisions to improve ER, parameter α can be decreased. In MECM, we can also reduce the value of parameter γ to accomplish the same purpose. Although both α and γ have effect on imprecise clusters in MECM, the mechanisms they work are different. Parameter α tries to adjust the penalty degree to control the imprecise rates of the results. However, for γ, the same aim could be got by regulating the uncertainty degree of imprecise classes. It can be seen from the figures, the effect of γ is more conspicuous than α. Moreover, although α may be set too high to obtain good clusterings, "good" partitions can also be got by adjusting γ in this case. For both MECM and ECM, the stable limiting values of evidential measures are around 0.7 and 0.8. Such values suggest the equivalence of the two methods to a certain extent. Parameter η is used for discounting the distance between uncertain objects and specific clusters. As pointed out in Fig. 3-c, if γ and α are well set, it has little effect on the final clusterings. The same is true in the case of δ which is applied to detect outliers. The effect of the different values of parameter β is illustrated in Fig. 3-d. We can see that it has little influence on the final results as long as it is larger than 1. As in FCM and ECM, for which it is a usual choice, we use β = 2 in all the following experiments.

The improvement of precision will bring about the decline of recall, as more data could not be clustered into specific classes. What we should do is to set parameters based on our own requirement to make a tradeoff between precision and recall. For instance, if we want to make a cautious decision in which EP is relatively high, we can reduce γ and α. Values of these parameters can be also learned from historical data if such data are available.

For the objects in the overlapped area, it is difficult to make a hard decision i.e. to decide about their specific groups. Thanks to the imprecise clusters, we can make a soft decision. As analysed before, the soft decision will improve the precision of total results and reduce the risk of misclassifications caused by simply partitioning the overlapped objects into specific class. However, too many imprecise decisions will decrease the recall value. Therefore, the ideal partition should make a compromise between the two measures. Set α = 1.8, γ = 0.2, η = 0. As it can be seen, for different overlap rates, the classical measures such as precision, recall, and RI are almost the same for all the methods. This reflects that pignistic probabilities play a similar role as fuzzy membership. But we can see that for MECM, EP is significantly high, and the increasing of overlap rates has least effects on it compared with the other methods. Such effect can be attributed to the introduced imprecise clusters which enable us to make a compromise decision between hard ones. But as many points are clustered into imprecise classes, the evidential recall value is low.

Overall, this example reflects one of the superiority of MECM that it can detect overlapped clusters. The objects in the overlapped area could be clustered into imprecise classes by this approach. Other possible available information or special techniques could be utilised for these imprecise data when we have to make hard decisions. Moreover, partitions with different degree of imprecision can be got by adjusting the parameters of the algorithm based on our own requirement.

Classical data sets from Gaussian mixture model

In the second experiment, we test on a data set consisting of 3 × 50 + 2 × 5 points generated from different Gaussian distributions. The first 3 × 50 points are from Gaussian distributions MECM is applied with the following settings: α = 1, δ = 100, η = 0.7, while ECM has been tested using α = 1.7, δ = 100 (The appropriate parameters can be determined similarly as in the first example). One can see from Figs. 5-b and 5-c , MCM and MFCM can partition most of the regular data in ω 1 , ω 2 and ω 3 into their correct clusters, but they could not detect the noisy points correctly. These noisy data are simply grouped into a specific cluster by both approaches. As can be seen from Fig. 5-d, for the points located in the middle part of ω 2 , ECM could not find their exact group and misclassify them into imprecise cluster ω 13 . In the figures ω ij {ω i , ω j } denotes imprecise clusters.

G(µ k , Σ k )(k = 1, 2, 3) with µ 1 =(0, 0) T , µ 2 = (40, 40) T , µ 3 = (80, 80) T ( 47
)
Σ 1 = Σ 2 = Σ 3 = ( 120
As mentioned before, imprecise classes in MECM can measure ignorance and uncertainty at the same time, and the degree of ignorance in meta clusters can be adjusted by γ. We can see that MECM does not detect many points in the overlapped area between two groups if γ is set to 0.6. In such a case the test objects are partitioned into imprecise clusters mainly because of our ignorance about their specific classes. These objects attributed to meta classes mainly belong to noisy data in ω 4 and ω 5 . The distance of these points to the prototypes of specific clusters is large (but not too large or they could be regarded to be in the emptyset, see Fig. 5-e). Thus the distance between the prototype vectors is relatively small so that these specific clusters are indistinguishable. Decreasing γ to be 0.2 would make imprecise class denoting more uncertainty, as it can be seen from Fig. 5-f, where many points located in the margin of each group are clustered into imprecise classes. In such a case, meta classes rather reflect our uncertainty on the data objects' specific cluster.

The table Tab. 2 lists the indices for evaluating the different methods. Bold entries in each column of this table (and also other tables in the following) indicate that the results are significant as the top performing algorithm(s) in terms of the corresponding evaluation index. We can see that the precision, recall and RI values for all approaches are similar except from those obtained for ECM which are significantly lower. As these classical measures are based on the associated pignistic probabilities for evidential clusterings, it seems that credal partitions can provide the same information as crisp and fuzzy ones. But from the same table, we can also see that the evidential measures EP and ERI obtained for MECM are higher (for hard partitions, the values of evidential measures equal to the corresponding classical ones) than the ones obtained for other methods. This fact confirms the accuracy of the specific decisions i.e. decisions clustering the objects into specific classes. The advantage can be attributed to the introduction of imprecise clusters, with which we do not have to partition the uncertain or unknown objects into a specific cluster. Consequently, it could reduce the risk of misclassification. However, although ECM also deals with imprecise clusters, the accuracy is not improved as much as in the case of applying MECM. As illustrated before in the case of ECM application, many objects of a specific cluster are partitioned into an irrelevant imprecise class and, as a result, the evidential precision value and ERI decrease as well. We also test on "Iris flower", "cat cortex" and "protein" data sets [START_REF] Fisher | The use of multiple measurements in taxonomic problems[END_REF][START_REF] Graepel | Classification on pairwise proximity data[END_REF][START_REF] Hofmann | Pairwise data clustering by deterministic annealing[END_REF]. The first is object data while the other two are relational data sets. Thus we compare our method with FCM and ECM for the Iris data set, and with RECM and NRFCM (Non-Euclidean Relational Fuzzy

Clustering Method [START_REF] Hathaway | Nerf c-means: Non-euclidean relational fuzzy clustering[END_REF]) for the last two data sets. The results are displayed in Fig. 6.

Presented results allow us to sum up the characteristics of MECM. Firstly, one can see that the behavior of MECM is similar to ECM for traditional data. Besides, credal partitions provided by MECM allow to recover the information of crisp and fuzzy partitions. Moreover, we are able to balance influence of our uncertainty and ignorance according to the actual needs. The examples utilised before deal with classical data sets. But the superiority of MECM makes it applicable in the case of data sets for which only dissimilarity measures are known e.g. social networks. Thus in the following experiments, we will use some graph data to illustrate the behaviour of the proposed method on the community detection problem in social networks. The dissimilarity index used here is the one brought forward by Zhou [START_REF] Zhou | Distance, dissimilarity index, and network community structure[END_REF]. To have a fair comparison, in the following experiments, we also compare with three classical algorithms for community detection i.e. BGLL [START_REF] Blondel | Fast unfolding of communities in large networks[END_REF], LPA [START_REF] Raghavan | Near linear time algorithm to detect community structures in large-scale networks[END_REF] and ZFCM (a fuzzy c-means based approach proposed by Zhang et al. [START_REF] Zhang | Identification of overlapping community structure in complex networks using fuzzy c-means clustering[END_REF]). The obtained community structures are compared with known performance measures, i.e., NMI (Normalized Mutual Information), VI (Variation of Information) and Modularity.

Artificial graphs and generated benchmarks

To show the performance of the algorithm in detecting communities in networks, we first apply the method to a sample network generated from Gaussian mixture model. This model has been used for testing community detection approaches by Liu and Liu [START_REF] Liu | Detecting community structure in complex networks using simulated annealing with k-means algorithms[END_REF].

The artificial graph is composed of 3

× 50 nodes, n 1 , n 2 , • • • , n 150 ,
Σ 1 = Σ 2 = Σ 3 = ( 0.25 0 0 0.25 ) . (49)
Then, the edges of the graph are generated by the following thresholding strategy:

if |x i -x j | ≤ dist,
we set an edge between node i and node j; Otherwise the two nodes are not directly connected. The graph is shown in Fig. 7-a (with dist = 0.8) and the dissimilarity matrix of the nodes is displayed in Fig. 7-b. From the figures we can see that there are three significant communities in the graph, and some nodes in the bordering of their groups seem to be in overlapped classes as they contact with members in different communities simultaneously.

The table Tab. 3 lists the indices for evaluating the results. It shows that MECM performs well as the evidential precision resulting from its application is high. MECM utilization also results in decreasing the probabilities of clustering failure thanks to the introduction of imprecise clusters.

This makes the decision-making process more cautious and reasonable.

The algorithms are also compared by means of Lancichinetti et al. [START_REF] Lancichinetti | Benchmark graphs for testing community detection algorithms[END_REF] benchmark (LFR)

networks. The results of different methods in two kinds of LFR networks with 500 and 1000 nodes are displayed in Figs. 8-9 respectively. The parameter µ showed in the x-axis in the figures identifies whether the network has clear communities. When µ is small, the graph has well community structure. In such a case, almost all the methods perform well. But we can see that when µ is partition the nodes into a specific cluster are of great confidence. In terms of NMI, the results are similar to those by BGLL and LPA, but better than those of MCM and MFCM. This fact well explains that the hard or fuzzy partitions could be recovered when necessary.

Some real-world networks

A. Zachary's karate club. The Zachary's Karate Club data [START_REF] Zachary | An information flow model for conflict and fission in small groups[END_REF] is an undirected graph which consists of 34 vertices and 78 edges. The original graph and the dissimilarity of the nodes are shown in Fig. 10-a and 10-b respectively.

Let the parameters of MECM be α = 1.5, δ = 100, η = 0.9, γ = 0.6. The modularity functions by MECM, MCM, MFCM and ZFCM (Fig. 12-a) peak around c = 2 and c = 3. Let c = 2, all the methods can detect the two communities exactly. If we set c = 3, a small community, which can also be found in the dissimilarity matrix (Fig. 10-b), is separated from ω 1 by all the approaches (see Fig. 11). But ZFCM assigns the maximum membership to ω 1 for node 9, which is actually in ω 2 . It seems that the loss of accuracy in the mapping process may cause such results.

MECM does not find imprecise groups when γ = 0.6 as the network has apparent community structure, and this reflects the fact that the communities are distinguishable for all the nodes.

But there may be some overlap between two communities. The nodes in the overlapped cluster can be detected by decreasing γ (increasing the uncertainty for imprecise communities). As is displayed in Fig. 11-c andd, by declining γ to 0.1 and 0.05 respectively (the other parameters remain unchanged), nodes 3 and 9 are clustered into both ω 1 and ω 2 (ω 12 ) one after another.

From the results we can see that MECM takes both the ignorance and the uncertainty into consideration while introducing imprecise communities. The degree of ignorance and uncertainty could be balanced through adjusting γ. The analysis shows that there appears only uncertainty without ignorance in the original club network. In order to show the performance of MECM when there are noisy conditions such that some communities are indistinguishable, two noisy nodes are added to the original graph in the next experiment.

B. Karate club network with some added noisy nodes. In this test, two noisy nodes are added to the original karate club network (see Fig. 13-a). The first one is node 35, which is directly connected with nodes 18 and 27. The other one is 36, which is connected to nodes 1 and 33. It can be seen from the dissimilarity matrix that node 36 has stronger relationships with both communities than node 35. This is due to the fact that the nodes connected to node 36 play leader roles in their own group, but node 35 contacts with two marginal nodes with "small" or insignificant roles in their own group only.

The results obtained by the application of different methods are shown in Fig. 14. The MECM parameters are set as follows: α = 1.5, δ = 100, η = 0.9 and γ is tuned according to the the extent that the imprecise communities reflect our ignorance. and uncertainty (other nodes).

These results reflect the difference between ignorance and uncertainty. As node 35 is only related to one outward node of each community, thus we are ignorant about which community it really belongs to. On the contrary, node 36 connects with the key members (playing an important role in the community), and in this case the dissimilarity between the prototypes of ω 1 and ω 2 is relatively large so they are distinguishable. Thus there is uncertainty rather than ignorance about which community node 36 is in. In this network, node 36 is a "good" member for both communities, whereas node 35 is a "poor" member. It can be seen from Fig. 15-a that the fuzzy partition by MFCM also gives large similar membership values to ω 1 and ω 2 for node 35, just like in the case of such good members as node 36 and 9. The obtained results show the problem of distinguishing between ignorance and the "equal evidence" (uncertainty) for fuzzy partitions. But Fig. 15-b shows that the credal partition by MECM assigns small mass belief to ω 1 and ω 2 for node 35, indicating our ignorance on its situation.

We also test our method on four other real-world graphs: American football network, Dolphins network, Lesmis network and Political books network1 . The measures applied to evaluate the performance of different methods are listed in Tab. 4-7. It can been seen from the tables, for all the graphs MECM application results in a community structure with high evidential precision level. The precision results from a cautious decision making process which clusters the noisy nodes into imprecise communities. In terms of classical performance measures like NMI, VI and modularity, MECM slightly outperforms the other algorithms. Note that these classical measures for hard partitions are calculated by the pignistic probabilities associated with the credal partitions provided by MECM. Therefore, we can also see the possibility to recover the hard decisions here when using the proposed evidential detection approach.

Discussion

We will discuss for which application MECM is designed here. As analysed before, for MECM only dissimilarities between objects are required and only the intuitive assumptions need to be satisfied for the dissimilarity measure. Therefore, the algorithm could be appropriate for many clustering tasks for non-metric data objects. This type of data is very common in social sciences, psychology, etc, where any metric assumptions about the similarities/dissimilarities could not be assured. The freedom for the data set leads to the restriction that the prototypes should be the objects themselves. Nevertheless, this constraint seems reasonable for social networks as the center of a community is usually the person (node) frequently contacting with others. Thus the approach can be applied to community detection problems. Thanks to the introduction of imprecise classes, it could reduce the risk of partitioning the objects which we are uncertain or ignorant into an incorrect cluster. For this reason the algorithm can help us make soft decisions when clustering the data set without distinct cluster/community structures or with overlap.

Due to the computational complexity, the proposed algorithm is not well directly adapted to handle very large data sets. However, here we discuss the possibility to apply the evidential community detection approach to large-scale networks. Firstly, the number of parameters to be optimized is exponential and depends on the number of clusters [START_REF] Masson | ECM: An evidential version of the fuzzy c-means algorithm[END_REF]. For the number of classes larger than 10, calculations are not tractable. But we can consider only a subclass with a limited number of focal sets [START_REF] Masson | ECM: An evidential version of the fuzzy c-means algorithm[END_REF]. For instance, we could constrain the focal sets to be composed of at most two classes (except Ω). Secondly, for the network with millions of nodes, MCM or MFCM could be evoked as a first step to merge some nodes into small clusters. After that we can apply MECM to the "coarsened" network. But how to define the edges or connections of the new graph should be studied. Lastly we emphasize that the evidential community detection algorithm could be utilised for gaining a better insight into the network structure and detecting the imprecise classes. For the large-scale network, it is difficult to make specific decisions for all of nodes due to the limitation of time, money or techniques. In this case we can use the proposed approach to make some "soft" decisions first and then use some techniques special for the imprecise parts of the graph.

Conclusion

We Therefore, it is not restricted to a metric space application. The prototypes of the clusters are constrained to the data objects themselves. MECM provides us with not only credal partitions but As mentioned in this paper, there may be more than one center in each community network.

Nevertheless, we ignore "multi-center" to avoid the troubles brought by the need for an initial seed using ESC and the definition of a threshold to control the distance between prototypes. We are aware that this is a drawback of the presented approach as not all the centers in each community are taken into consideration. Therefore, we intend to include the feature of multiple centers in our future research work.

• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • ω 1 ω 2 ω 3
a. Gaussian network b. Dissimilarity matrix

  There are two types of correct decisions by the clustering result: a true positive (TP) decision assigns two similar objects to the same cluster, while a true negative (TN) decision assigns two dissimilar objects to different clusters. Correspondingly, there are two types of errors we can commit: a false positive (FP) decision assigns two dissimilar objects to the same cluster, while a false negative (FN) decision assigns two similar objects to different clusters. Let a (respectively, b) be the number of pairs of objects simultaneously assigned to identical classes (respectively, different classes) by the stand reference partition and the obtained one. Actually a (respectively, b) is the number of TP (respectively, TN) decisions. Similarly, let c and d be the numbers of FP and FN decisions respectively. Two popular measures that are typically used to evaluate the performance of hard clusterings are precision and recall. Precision (P) is the fraction of relevant instances (pairs in identical groups in the clustering benchmark) out of those retrieved instances (pairs in identical groups of the discovered clusters), while recall (R) is the fraction of relevant instances that are retrieved. Then precision and recall can be calculated by P = a a + c and R = a a + d[START_REF] Yang | Hierarchical community detection with applications to real-world network analysis[END_REF]

Fig. 1 -

 1 Fig. 1-b -1-d. The values of the six evidential indices (P,R,RI,EP,ER,ERI) are listed in Tab. 1.

Figure 1 :

 1 Figure 1: An small data set with imprecise classes.

Figure 2 :

 2 Figure 2: Clustering of overlapped data set

  7 and δ = 50, the "best" (with relatively high values on both precision and recall) clustering result by MECM is shown in Fig. 2-b. As we can see, most of the data in the overlapped area are partitioned into imprecise cluster ω 12 {ω 1 , ω 2 } by the application of MECM. We adjust the coordinates of the center of the second circle to get overlapped data with different proportions (overlap rates), and the validity indices of the clustering results by different methods are illustrated in Fig. 4. For the application of MECM, MCM and MFCM, each algorithm is evoked 20 times with randomly selected initial prototypes for the same data set and the mean values of the evaluating indices are reported. The figure Fig. 4-d shows the average values of the indices by MECM (plus and minus one standard deviation) for 20 repeated experiments as a function of the overlap rates. As we can see the initial prototypes indeed have effects on the final results, especially when the overlap rates are high. Certainly, we can avoid the influence by repeating the algorithm many times. But this is too expensive for MECM. Therefore, we suggest to use the prototypes obtained in MFCM or MCM as the initial. In the following experiments, we will set the initial prototypes to be the ones got by MFCM.

2 × 48 )Σ 4 = Σ 5

 24845 10 data are noisy points follow G(µ k , Σ k )(k = 4, 5) with µ 4 =(-50, 90) T , µ 5 = (-10, 130) T (

  which are represented by 150 sample points, x 1 , x 2 , • • • , x 150 , in two-dimensional Euclidean space. There are 3 × 50 points generated from Gaussian distributions G(µ k , Σ k )(k = 1, 2, 3) with µ 1 = (1.0,4.0) T , µ 2 = (2.5, 5.5) T , µ 3 = (0.5, 6.0) T

  introduced a Median variant of Evidential C-means (MECM) as a new prototype-based clustering algorithm in the present contribution. The proposed approach is an extension of median c-means and median fuzzy c-means. It is based on the framework of belief function theory. The applied median-based clustering requires the definition of the dissimilarity between the objects only.

Figure 4 :

 4 Figure 4: Clustering of overlapped data set with different overlap rates. Figure-d shows the average values of the indices (plus and minus one standard deviation) for 20 repeated experiments, as a function of the overlap rates. For MECM α = 1.8, γ = 0.2, η = 0.7, δ = 50.

Figure 5 :

 5 Figure 5: Clustering of the artificial data set by different methods

Figure 6 :

 6 Figure 6: Clustering results of different data sets

Figure 7 :

 7 Figure 7: Artificial network from Gaussian mixture model

Figure 9 :

 9 Figure 9: Comparison of MECM and other algorithms in LFR networks. The number of nodes is N = 1000. The average degree is |k| = 20, and the pair for the exponents is (γ, β) = (2, 1).

  karate club network b. Dissimilarity matrix

Figure 10 :Figure 11 :

 1011 Figure 10: Original karate club network

Figure 12 :

 12 Figure 12: Modularity functions of karate club network by different methods

Figure 13 :Figure 14 :

 1314 Figure 13: Karate club network with two noisy nodes

Figure 15 :

 15 Figure 15: Fuzzy membership and mass belief of the nodes in karate club network with noisy nodes

Table 1 :

 1 Evaluation Indices of the partitions.

Table 2 :

 2 The clustering results for gaussian points by different methods. For each method, we generate 20 data sets with the same parameters and report the mean values of the evaluation indices for all the data sets.

		Precision	Recall	RI	EP	ER	ERI
	MCM	0.7802	0.9570	0.9002	0.7802	0.9570	0.9002
	MFCM	0.8616	0.9797	0.9484	0.8616	0.9797	0.9484
	FCM	0.8644	0.9820	0.9500	0.8644 0.9820	0.9500
	ECM	0.8215	0.9353	0.9222	0.9069	0.8436	0.9294
	MECM (γ = 0.2)	0.8674 0.9855 0.9520 0.9993	0.7721	0.9336
	MECM (γ = 0.6)	0.8662	0.9851	0.9515	0.9958	0.9586 0.9868

Table 3 :

 3 The results for Gaussian graph by different methods

		Precision	Recall	RI	EP	ER	ERI	NMI	VI Modularity
	MCM	0.9049	0.9110	0.9392	0.9049 0.9110	0.9392	0.8282	0.3769	0.6100
	MFCM	0.9067	0.9099	0.9396	0.9067 0.9099	0.9396	0.8172	0.4013	0.6115
	ZFCM	0.9202	0.9224	0.9482	0.9202 0.9224	0.9482	0.8386	0.3545	0.6118
	MECM	0.9470 0.9472 0.9652 0.9789 0.6060	0.8661 0.8895 0.2428	0.6072
	BGLL	0.9329	0.9347	0.9564	0.9329 0.9347 0.9564	0.8597	0.3081	0.6119
	LPA	0.3289	1.0000	0.3289	0.3289 1.0000	0.3289	0.0000	1.0986	0.0000
	large, the results by MECM have the largest values of precision. It means that the decisions which

  As we can see, MCM, MFCM and ZFCM simply group the two noisy nodes into ω 1 . With γ = 0.4 MECM regards node 36 as a member of ω 1 while node 35 is grouped into imprecise community ω 12 . And ω 12 mainly reflects our ignorance rather than uncertainty on the actual community of node 36. This is why node 36 is not clustered into ω 12 since ω 1 and ω 2 are distinguishable for him but we are just not sure for the final decision.The increase in the extent of uncertainty in imprecise communities results from the decrease of γ value. We can see that more nodes (including nodes 36,9,1,12,27, see Figs.14-e and f) are clustered into ω 12 or ω 13 due to uncertainty. The imprecise communities consider both ignorance (node[START_REF] Newman | Finding and evaluating community structure in networks[END_REF]

Table 4 :

 4 The results for American football network by different methods

		Precision	Recall	RI	EP	ER	ERI	NMI	VI Modularity
	MCM	0.7416	0.8834	0.9661	0.7416	0.8834	0.9661	0.8637	0.6467	0.5862
	MFCM	0.7583	0.8757	0.9678	0.7583	0.8757	0.9678	0.8715	0.6160	0.5745
	ZFCM	0.8176	0.9082	0.9765	0.8176	0.9082	0.9765	0.9035	0.4653	0.6022
	MECM	0.8232	0.9082 0.9771 0.9303	0.8681 0.9843 0.9042 0.4625	0.5995
	BGLL	0.7512 0.9120	0.9689	0.7512 0.9120	0.9689	0.8903	0.5195	0.6046
	LPA	0.6698	0.8298	0.9538	0.6698	0.8298	0.9538	0.8623	0.6580	0.5757

Table 5 :

 5 The results for Dolphins network by different methods

		Precision Recall	RI	EP	ER	ERI	NMI	VI Modularity
	MCM	1	1	1	1	1	1	1	0	0.3787
	MFCM	1	1	1	1	1	1	1	0	0.3787
	ZFCM	1	1	1	1	1	1	1	0	0.3787
	MECM	1	1	1	1	1	1	1	0	0.3787
	BGLL	0.9271 0.3583 0.6351 0.9271 0.3583 0.6351 0.4617 1.1784	0.5185
	LPA	0.9250 0.5029 0.7070 0.9250 0.5029 0.7070 0.5595 0.8354	0.5070

Table 6 :

 6 The results for Lesmis network by different methods

		Precision	Recall	RI	EP	ER	ERI	NMI	VI Modularity
	MCM	0.6109	0.5522	0.9005	0.6109	0.5522	0.9005	0.7381	1.1295	0.4732
	MFCM	0.5774	0.6456	0.8971	0.5774	0.6456	0.8971	0.7743	0.9555	0.4705
	ZFCM	0.7368	0.5769	0.9217	0.7368	0.5769	0.9217	0.7805	0.9666	0.4983
	MECM	0.7065	0.7473 0.9299 0.9298	0.4368 0.9258 0.7977 0.8531	0.4884
	BGLL	0.5796	0.8104	0.9033	0.5796	0.8104	0.9033	0.7551	0.9435	0.5556
	LPA	0.4594 0.9643	0.8544	0.4594 0.9643	0.8544	0.7500	0.8637	0.5428

Table 7 :

 7 The results for Political books network by different methods ignorance from uncertainty while the fuzzy or crisp partitions could not. By the introduced imprecise clusters, we could find some overlapped and indistinguishable clusters for related nodes. Thanks to the advantages of belief function theory and median clustering, MECM could be applied to community detection problems in social networks. As other median clustering approaches, MECM tends to get stuck in local minima such that several runs have to be performed to obtain good performance. However, we propose an initial prototype-selection scheme using the evidential semi-centrality for the application of MECM in community detection to solve the problems brought by the initial prototypes. Results of presented experiments on artificial and realworld networks show that the credal partitions on graphs provided by MECM application are more refined than crisp and fuzzy ones. Therefore, they could enable us to gain a better understanding of analysed community structure. Some examples on the classical metric space are also given to illustrate the interest of MECM and to show its difference with respect to the existing methods.

		Precision	Recall	RI	EP	ER	ERI	NMI	VI Modularity
	MCM	0.8109	0.8030	0.8482	0.8109	0.8030	0.8482	0.5721	0.8426	0.4979
	MFCM	0.8020	0.8187 0.8485	0.8020	0.8187 0.8485 0.5755	0.8256	0.4962
	ZFCM	0.7928	0.7487	0.8234	0.7928	0.7487	0.8234	0.5301	0.9407	0.5048
	MECM	0.7880	0.8081	0.8383 0.8458	0.6435	0.8128 0.5755	0.8247	0.4725
	BGLL	0.8244	0.6203	0.7978	0.8244	0.6203	0.7978	0.5121	1.0987	0.5205
	LPA	0.7331 0.8558	0.8200	0.7331 0.8558	0.8200	0.5612 0.7925	0.4604
	also hard and fuzzy partitions as by-products through computing pignistic probabilities. Moreover,
	it could distinguish

  Figure 8: Comparison of MECM and other algorithms in LFR networks. The number of nodes is N = 500. The average degree is |k| = 15, and the pair for the exponents is (γ, β) = (2, 1).

		1.0									1.0								MECM
																			MCM
																			MFCM
																			BGLL
		0.8									0.8								LPA
											0.6
	EP	0.6								NMI	0.4
		0.4
											0.2
			MECM
		0.2	MCM MFCM								0.0
			BGLL
			LPA
		0.1	0.2 0.2	0.3	0.4 0.4	0.5	0.6 0.6	0.7	0.8 0.8	0.9	0.1	0.2 0.2	0.3	0.4 0.4	0.5	0.6 0.6	0.7	0.8 0.8	0.9
						µ									µ
					a. Precision								b. NMI
		1.0									1.0
		0.8									0.8
		0.6									0.6
	EP									NMI
		0.4									0.4
		0.2									0.2
			MECM									MECM
			MCM									MCM
			MFCM									MFCM
		0.0	BGLL								0.0	BGLL
			LPA									LPA
		0.1	0.2 0.2	0.3	0.4 0.4	0.5	0.6 0.6	0.7	0.8 0.8	0.9	0.1	0.2 0.2	0.3	0.4 0.4	0.5	0.6 0.6	0.7	0.8 0.8	0.9
						µ									µ
					a. Precision								b. NMI

These data sets can be found in http://networkdata.ics.uci.edu/index.php

Acknowledgements

The authors are grateful to the anonymous reviewers for all their remarks which helped us to clarify and improve the quality of this paper. This work was supported by the National Natural Science Foundation of China (Nos.61135001, 61403310).


Hector Romero Ugalde

Virginie Le Rolle

Alain Bel

Jean-Luc Bonnet

David Andreu

Philippe Mabo

Guy Carrault

Alfredo I Hernández

On-off closed-loop control of vagus nerve stimulation for the adaptation of heart rate

Vagus nerve stimulation (VNS) is a potential therapeutic approach in a number of clinical applications. Although VNS is commonly delivered in an open-loop approach, it is now recognized that closed-loop approaches may be necessary to optimize the therapy and minimize side effects of neuro-stimulation devices. In this paper, we describe a prototype system for real-time control of the instantaneous heart rate, working synchronously with the heart period. As a first step, an on-off control method has been integrated. The system is evaluated on one sheep with induced heart failure, showing the interest of the proposed approach.

I. INTRODUCTION

Vagus nerve stimulation (VNS) has been identified as a potential therapeutic approach in a number of clinical applications, such as epilepsy, supra-ventricular arrhytmias and heart failure (HF) [1]- [START_REF] Li | Vagal nerve stimulation markedly improves long-term survival after chronic heart failure in rats[END_REF]. Although VNS is commonly delivered in an open-loop approach, it is now recognized that adaptive, closed-loop approaches may be necessary to optimize the therapy and minimize side effects of neuro-stimulation devices [START_REF] Pattent | A1: System for abating neural stimulation side effects[END_REF]- [START_REF] Tosato | Closed-loop control of the heart rate by electrical stimulation of the vagus nerve[END_REF]. A variety of physiological data may be employed as control variables in a closed-loop approach, depending on the target function of VNS control. Previous works in the literature have been mainly focused on the control of heart rate, since this variable is particularly important and is readily observable.

To our knowledge, the first attempt to provide a closed-loop VNS approach was proposed by Bilgutay et al. [4]. In their paper, three models of "vagal tuners" are proposed. Two of them are implantable, but manually activated. The third one is an external device, which is automatically activated when the RR interval falls bellow a threshold value. In such vagal tuners, VNS is delivered synchronously with the R-wave, detected from the ECG signal. Although the two manual approaches have been developed and evaluated on 10 dogs, no details are given on the development or evaluation of the automatic approach.

Other closed-loop systems for VNS control, based on the adaptation of the VNS frequency are proposed in [START_REF] Waninger | Electrophysiological control of ventricular rate during atrial fibrillation[END_REF] and [START_REF] Tosato | Closed-loop control of the heart rate by electrical stimulation of the vagus nerve[END_REF]. In [START_REF] Waninger | Electrophysiological control of ventricular rate during atrial fibrillation[END_REF], a control system, based on the classical cumulative sum control chart technique, adjusts stimulation frequency in order to regulate the average ventricular rate during atrial fibrillation in dogs. VNS is delivered continuously to the left vagus nerve, without any cardiac beat synchronization. Initially, the stimulation is delivered at a nominal frequency of 1 pulse/s and then the controller automatically updates the left vagal stimulation frequency. The other stimulation parameters have been manually defined and fixed during the whole test for each dog (pulse width = 1 ms and current = 2 -5 mA).

Tosato et al. [START_REF] Tosato | Closed-loop control of the heart rate by electrical stimulation of the vagus nerve[END_REF] use a proportional-integral (PI) controller, which also adjusts the stimulation frequency, in order to regulate heart rate in pigs. In their work, different tests are presented, including the stimulation of the left, right and both vagus nerves. For each test, a different stimulation amplitude is kept constant in the range 4 -15 mA, the pulse width is fixed to 0.3 ms and the controller automatically updates the "optimal" stimulation frequency within the range 0 -20 Hz in three pigs and 0 -25 Hz in four pigs. The update rate of the controller is kept constant within a test, but varies for each test within 10 to 60 updates/s and the stimulation is delivered asynchronously.

In this paper, we describe a prototype system for real-time control of the instantaneous heart rate of a sheep with induced heart failure, through adaptive vagus nerve stimulation. The ovine animal model has been chosen, since it is particularly robust to the induction of heart failure through myocardial infarction. As opposed to the above-mentioned methods, the proposed approach works synchronously with the heart period, which implies additional constraints. As a first step, we have integrated an on-off control method, in which the burst of VNS pulses are conditionally delivered to the right vagus nerve, 50 ms after an R-wave is detected from the ECG.

The paper is organized as follows: First we describe the sheep preparation and the on-off closed-loop control system used in this work. In Section III, the paper discuses the results obtained in the different tests applied to our control system. Finally conclusions are given in Section V.

II. METHODS

A. Sheep preparation

The present study was conducted under the approval issued by the French ethics committee for animal experimentation. Heart failure was induced in one sheep (body weight 35 kg) by occluding 3 marginal and 1 diagonal coronary arteries. During the same intervention, a bipolar pacemaker lead containing an intracardiac accelerometer was placed in the right ventricle (SonRTip T M lead, Sorin CRM, Clamart, France) and a cuff-type VNS electrode (Cuff electrode C4D3-1, Obelia) was implanted on the right vagus nerve, at a cervical site. Three months after inclusion, the ejection fraction of this sheep was measured at 38 %, confirming HF induction. A new experimentation was then performed in order to test the VNS control system.

During this second intervention, the sheep was initially anesthetized with Propofol and a morphine bolus. After this initial phase, the sheep was anesthetized by Etomidate (100 µg/kg/min). The surface ECG, the intracadiac ElectroGraMs (EGM), the left intra-ventricular pressure and the body temperature (37 o C) were monitored during the whole procedure. Breathing was artificially controlled at 0.3 Hz (18 breath/ min). After a verification stage of the implanted instrumentation (in particular VNS electrode impedance and EGM quality), the evaluation experiment of the proposed control system, described in Section II-C, was implemented.

B. On-off closed-loop control system

The closed-loop control system (see Fig. 1) comprises: 1) a bipolar sensor (SonRTip T M lead, Sorin CRM, Clamart, France), placed in the right ventricle, in order to acquire the EGM, 2) a cuff-type VNS electrode (Cuff electrode C4D3-1, Obelia), implanted on the right vagus nerve, at a cervical site and used for vagus nerve stimulation, 3) the prototype (Proto INTENSE V 1.2) which contains a neurostimulator device and an analog signal conditioning unit (EGM), 4) a data acquisition (DAQ) device NI USB-6211, and 5) an application developed on LabView, which receives and process the EGM signal in real time and implements the VNS control loop method. In the current development version of the stimulator, we do not have programmatic, real-time access to all stimulation parameters. Only a "trig in" feature is available (see Fig. 1), which allows us to precisely activate a pre-programmed VNS profile. With this constraints in mind, the following control application, based on a classical on-off approach, was developed in LabView. Fig. 2 shows the algorithm on which our application is based. Real-time R-wave detection is applied to the measured EGM signals, to estimate the instantaneous RR interval (and the instantaneous heart rate, HR). If the current RR interval is lower than the minimal target RR value, then the stimulator is set to on, i.e. the pre-programmed stimulation profile is delivered. If the current RR interval is greater than the minimal target RR, the stimulator is set to off, i.e. no stimulation is delivered.

The EGM signal is acquired using a NI USB-6211 data acquisition (DAQ) device. The analog signal activating the "Trig in" input of the neurostimulator is sent by using an analog output of the same DAQ device.

C. Experimental application of the control system

Experiments were performed in three steps: 1) Before starting the control system, different VNS configurations are applied, in order to evaluate, for each one, its impact on the instantaneous RR, for a given sheep. 2) A VNS configuration showing a sufficient variation on HR (RR during stimulation -RR before stimulation > 200 ms) is selected and programmed into the stimulator.

3) The control system is activated, with different target HR values. For this sheep, the pre-programmed VNS configuration was the following: frequency = 31 Hz, delay from R-wave = 50 ms, pulse width = 0.24 ms, and current amplitude = 2 or 3 mA.

III. RESULTS AND DISCUSSION

In order to validate the proposed on-off control system, four tests are presented in this section. For all these tests the VNS frequency is fixed to 31 Hz and the pulses are delivered conditionally, 50 ms after an R-wave is detected.

A. Test 1: Minimal target RR = 500 ms, VNS current = 3 mA, Number of pulses = 2.

In the first test, the objective is to reach a minimal RR of 500 ms. The stimulation current is set to 3 mA and two pulses are delivered. Results are presented in Fig. 3, which presents the detected instantaneous RR intervals with respect to beat number, before, during and after the application of the closed-loop VNS. Fig. 3 shows that the spontaneous RR interval of the sheep (around 480 ms) is significantly modified during the activation of the control system. The minimal target RR is reached with the selected stimulation parameters. However, the RR oscillations around the minimal target RR value are quite high. These oscillations are inherent to the on-off algorithm. In fact, when a stimulation is delivered with the pre-programmed parameters, the RR interval reaches values around 600 ms. When the stimulator is turned off, the RR interval tends to fall to the spontaneous RR interval (around 480 ms). According to the on-off algorithm presented above, when an R-wave is detected and the RR interval is lower than the minimal target RR, i.e. 500 ms in this example, then a stimulation is delivered and the minimal target RR is reached. Therefore, in the next R-wave the RR interval is greater than the minimal target RR and the stimulator is set off. For this reason, in this example, the stimulator switches on and off each time an R-wave is detected. We can observe in Fig. 3, beats from 118 to 122, that the VNS does not have the same effect as for the rest of the beats. This is due to normal physiological variations. In this sense, in the following test, we set the minimal target RR near to the maximal instantaneous RR values that the stimulator can reach with the pre-programmed stimulation parameters, we test how the on-off algorithm reacts to these oscillations.

B. Test 2:

Minimal target RR = 600 ms, VNS current = 3 mA, Number of pulses = 2.

In the second test (see Fig. 4), the minimal target RR is set to RR = 600 ms and the stimulation parameters are set as in the first test, i.e., the stimulation current is set to 3 mA and two pulses are delivered. In the third test a different set of parameters is pre-programmed, and the same objective is appointed, i.e., minimal target RR = 600 ms and two pulses are delivered. However, the stimulation current is reduced to 2 mA. The results of this test are displayed in Fig. 5.

With the stimulation parameters used in this test (Fig. 5) the minimal target RR can not be reached. Therefore, the stimulator is set on during the entire closed-loop VNS phase.

All the previous results show the importance of modifying the most sensitive VNS parameters within the control loop, in order to 1) minimize RR oscillations around a target RR interval and 2) cope with physiological variations of the RR response to the pre-programmed VNS profile. The following section presents results in which one of the most sensitive VNS parameters (number of VNS pulses) is modified manually during a test with dynamic target RR definitions.

D. Test 4: Manual dynamic modification of the number of VNS pulses

In order to improve our control system in a future work, we decide to test the effect of the number of VNS pulses in the instantaneous RR interval. As already mentioned, in the current version of the stimulator (Prototype INTENSE V 1.2), only a "trig-in" feature is available. With this constraint in mind, a new application was implemented in LabView. This application works as follows: 1) one pulse (pulse width = 0. 24 ms, current = 2 mA) is pre-programmed on the stimulator prototype, 2) the LabView application triggers the pre-programmed pulse N times at a frequency of 31 Hz, generating a VNS sequence of N pulses, pulse width = 0. 24 ms, current = 2 mA and frequency = 31Hz. Even if our perspective is, in a future work, to automatically adapt the VNS parameters, in this test, the number of pulses is manually changed. Fig. 6 shows the instantaneous RR response to varying minimal target RR and number of pulses. Beats from 35 to 100 (Fig. 6 b)) correspond to a minimal target RR = 500 ms and three pulses. After 100 beats, the minimal target RR is changed to 550 ms (Fig. 6 c)). At 145 beats, the minimal target RR is changed to 600 ms (Fig. 6 d)). Beats from 245 to 319 correspond to an unreached minimal target RR of 650 ms (Fig. 6 e)). Intended to reach the minimal target RR = 650 ms the number of delivered pulses is increased to four at beat 320 (Fig. 6 f)). For the beats from 35 to 145 (Fig. 6 b) and c)), there is not any difference in the RR response, even if the minimal target RR is changed from 500 ms to 550 ms and identical stimulation parameters are used. This is somehow normal, because when a stimulator is set on, the RR interval raises to values around 600 ms and when the stimulator is set off, the RR interval falls to values around 480 ms. Therefore, when the minimal target RR varies between these two limit values the same oscillations will occur.

When the minimal target RR is set to 600 ms and the same stimulation parameters are used (see Fig. 6 d)), the stimulator is set on during more than two consecutive R-waves. This test becomes similar to the second test.

When the minimal target RR is set to 650ms (see Fig. 6 e) and f)), the objective is never reached even if the number of delivered pulses is increased to four pulses at beat 320. Therefore the stimulator is set on during all these beats (245-370).

IV. ACKNOWLEDGMENTS

This work was partly supported by Bpifrance within the Investment for the Future program in France.

V. CONCLUSIONS

A VNS closed-loop control system is proposed in order to regulate the heart rate of a sheep with induced heart failure, in a beat-to-beat basis. Due to the hardware constraints of the current version of the stimulator, only an on-off approach was implemented. Experimental results confirm that closed-loop VNS, with the tested parameter configurations, significantly modifies the spontaneous RR interval. Nevertheless, results showed significant RR oscillations, inherent to the on-off algorithm. Such oscillations may be reduced by implementing a more advanced control algorithm, which will automatically adapt other VNS parameters.

Fig. 1 .

 1 Fig. 1. Closed-loop control system.

Fig. 2 .

 2 Fig. 2. LabView application: R-wave detection, RR calculator and on-off algorithm.

Fig. 3 .

 3 Fig.3. RR interval when the minimal target RR = 500 ms with the stimulations parameters 3 mA and 2 pulses.

Fig. 4 .

 4 Fig. 4. Minimal target RR=600 ms, 3 mA and 2 pulses.

Fig. 5 .

 5 Fig. 5. Minimal target RR=600 ms, 2 mA and 2 pulses.

Fig. 6 .

 6 Fig. 6. Instantaneous RR response to varying minimal target RR and number of pulses. a) Closed-loop VNS is off, b) Minimal target RR = 500 ms and number of pulses = 3, c) Minimal target RR = 550 ms and number of pulses = 3, d) Minimal target RR = 600 ms and number of pulses = 3, e) Minimal target RR = 650 ms and number of pulses = 3, f) Minimal target RR = 650 ms and number of pulses = 4. The pre-programmed stimulation parameters for this experiment were: frequency = 31 Hz, delay from R-wave = 50 ms, pulse width = 0.24 ms, and current amplitude = 2 mA.