Clustering using distance in fuzzy graphs.

Introduction

A fuzzy graph [1] is a pair G: ([sigma],([mu]) where [sigma] is a fuzzy subset of a set S and [mu] is a fuzzy relation on [sigma] such that [mu].(u, v) [less than or equal to] a(u) A [sigma] (v). We assume that S is finite and nonempty, [mu] is reflexive and symmetric[1]. Also, we denote the underlying crisp graph by [G.sub.*] : ([[sigma].sup.*], [[mu].sup.*]) where [[sigma].sup.*] = {u [member of] S : a(u) > 0} and [[mu].sub.*] = {(u,v) [member of] SXS : [mu](u, v) > 0}. A path P of length n is a sequence of distinct nodes [U.sub.0], [u.sub.1],.....[u.sub.n] such that [mu]([u.sub.i-1] ,[u.sub.1]) > 0,i = 1,2,......,n and the degree of membership of a weakest arc is defined as its strength.G : ([sigma], [mu]) is called a complete fuzzy graph if[mu](u,v) = [sigma](u)[LAMBDA] [sigma] (v) [for all] u,v. The strength of connectedness between two nodes x and y is defined as the maximum of the strengths of all paths between x and y and is denoted by [CONN.sub.G] (x, y). An x - y path P is called a strongest x - y path if its strength equals [CONN.sub.G](x, y)[2,3]. A fuzzy graph G : ([sigma], [mu]) is connected if for every x,y in [[sigma].sup.*], [CONN.sub.G](x, y) > 0.

The [mu]-distance [rho](u,v) is the smallest [mu]-length of any u-v path, where the [mu]-length of the path [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. If n=0, then l(P) = 0. In a connected fuzzy graph G, [rho](u, v) is a metric [1].

The [delta]--distance is defined as [delta](x,y) = 1 - [CONN.sub.G](x,y), [for all]x, y [member of] S where [delta] is a fuzzy relation defined from 5x S in to R. Clearly [delta] is a metric on S [2].

An arc of a fuzzy graph is called strong if its weight is at least as great as the connectedness of its end nodes when it is deleted and an x - y path P is called a strong path if P contains only strong arcs[3]. A strong path P from x to y is an x-y geodesic if there is no shorter strong path from x to y and the length of an x-y geodesic is the distance from x to y denoted by [d.sub.g](x,y) [4].

Cluster Analysis

Cluster analysis has been employed as an effective tool in scientific inquiry. One of its most useful roles is to generate hypotheses about category structure. Cluster analysis may be used to reveal structure and relations in the data. It is a tool of discovery. The results of cluster analysis can contribute directly to development of classification schemes. In other words it may be possible to reduce a very large body of data to a relatively compact description through cluster analysis. Graph theorists prefer 'partition' as a term describing a collection of clusters.

In graph theory, there are several ways of defining 'clusters' of vertices. One approach is to call a subset C of S a cluster of order k if the following two conditions hold; for all vertices x, y in C, d(x, y) [less than or equal to] k ; for all vertices z [not member of] C, d(z, w) > k for some w [member of] C ; where d(u, v) is the length of a shortest path between two vertices u and v.

Thus in a k-cluster C, all pairs of vertices are within distance k of each other, and C is maximal with respect to this property. That is no vertex outside of C is within a distance k of every vertex in C. For example,

Let G be a graph with node set, V = {x, y, z, u, v} and arc set E = {(x, y), (x, z), (y, z), (z, u), (u, v)}.

Here [C.sub.1] = {x, y, z} is a cluster of order 1.

For, d(x, y) [less than or equal to] 1, d(x,z) [less than or equal to] 1 and d(y,z) [less than or equal to] 1 and d(x, u) = 2, d(x,v) = 3,d(y,u) = 2, d(y,v) = 3, d(z,u) = 1 and d(z,v) = 2 [??] [C.sub.1] is a cluster of order 1.

Similarly [C.sub.2] = {x,y,z,u} is a cluster of order 2 and [C.sub.3] = {x,y,z,u,v} is a cluster of order 3.

Now in a fuzzy graph we replace the distance d(x, y) by the different distance functions such as, [delta]-distance, [mu]-distance and g-distance, we obtain clusters of order k, where k [member of] [0, 1] for [delta]-distance, k is a positive real number for [mu]-distance and k is a positive integer for g- distance. Note that a k-cluster C is an ordinary subset of S.

Example 1:

Let G: ([sigma], [mu]) be a fuzzy graph with [[sigma].sub.*] = {x, y, z, u, v} and [[mu].sup.*] = {(x, y), (x, z), (y, z), (z,u),(u, v)} with [mu] (x, y) = [mu](x, z) = [mu](y, z) = 0.5, [mu](z, u) = [mu](u, v) = 0.25.

The strength of connectivity and 5 -distance between pairs of nodes in G are expressed by the matrices M and D respectively as follows,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Here [C.sub.1] = {x, y, z} is a cluster of order 0.5. That is [delta](x,y) = 0.5 = [delta]{x,z) = [delta]{y,z)

Also [C.sub.2] = {x, y, z, u, v} is a cluster of order 0.75.

From Example 1, using [mu]-distance we have [rho](x,y) = 2,[rho](x,z) = 4,[rho](y,z) = 2,[rho](x,u) = 8,,[rho](x,v) = 12,[rho](y,u) = 6, [rho](y,v) = 10, [rho](z,u) = 4, [rho](z,v) = 8,[rho](u,v) =4

[C.sub.1] = {x,y},{y,z} is a cluster of order 2, [C.sub.2] = {x,y,z},{z,u},{u,v} is a cluster of order 4, [C.sub.3] = {x,y,z},{y,z,u},{u,v} is a cluster of order 6, [C.sub.4] = {x,y,z,u},{z,u,v} is a cluster of order 8, [C.sub.5] = {y,z,u,v},{x,y,z,u} is a cluster of order 10 and [C.sub.6] = {x,y,z,u,v} is a cluster of order 12.

Using g-distance(from Example 1) we have [d.sub.g](x,y)=1, [d.sub.g](x,z) = 2, [d.sub.g](x,u)=3, [d.sub.g](x,v) = 4, [d.sub.g](y,z)=1, [d.sub.g](y,u)=2, dg(y,v)=3, [d.sub.g](z,u)=1, [d.sub.g](z,v)=2 and [d.sub.g](u,v)=1.

Here [C.sub.1] = {x,y},{y,z},{z,u},{u,v} is a cluster of order 1, [C.sub.2] = {x,y,z}, {z,u,v} is a cluster of order 2, [C.sub.3] = {x,y,z,u}, {y,z,u,v} is a cluster of order 3 and [C.sub.4] = {x,y,z,u,v} is a cluster of order 4.

Next we introduce a method for finding clusters of order k using distance matrix of a fuzzy graph.

Construction of clusters of order k

Let D = ([d.sub.ij]) be the distance matrix of a fuzzy graph G: ([sigma],[mu]) of order n x n, where n is the number of nodes in G labeled as [u.sub.1],[u.sub.2],...[u.sub.n], and [d.sub.ij] is the distance between the nodes [u.sub.i] and [u.sub.j]. Since we consider only symmetric fuzzy graphs, the distance matrix is also symmetric so we concentrate on the upper triangular entries of D only.

Now obtain the set [R.sub.ik] corresponding to the [i.sup.th] row as,

[R.sub.ik] = {[u.sub.i]} [union] {[u.sub.j] / d([u.sub.i],[u.sub.j]}) [less than or equal to] k, j = i +1,.....n}

Next for each i = 1,2...n, and for each l = 1,2...n-i,

Define [C.sub.i [l.sub.k]] = {[u.sub.i]} [union] {[R.sub.ik] [intersection] [R.sub.(i+l)k]}.

Then the collection of all maximal sets in the family of sets [C.sub.i [l.sub.k], are clusters of order k.

Proof: Let G be a graph n nodes and D be the distance matrix of G. Let [C.sub.k] be the clusters of order k in G. Suppose not, that is there exist [u.sub.i], [u.sub.j] in [C.sub.k] such that d([u.sub.i],[u.sub.j]) > k, which contradict the construction of the set [R.sub.ik] where [R.sub.ik] = {[u.sub.i]} [union] {[u.sub.j] / d([u.sub.i] ,[u.sub.j]) [less than or equal to] k , j = i + 1,.....n}. There for d([u.sub.i] ,[u.sub.j]) [less than or equal to] k [for all] [u.sub.i],[U.sub.j] [member or] [C.sub.k]

Now for any [u.sub.r][not equal to] [C.sub.k] implies [u.sub.r] [R.sub.ik], ie d([u.sub.i], [u.sub.r]) > k.

There for any [u.sub.r] [not equal to] [C.sub.k], d([u.sub.i], [u.sub.r]) >k for some [u.sub.i] [member of] [C.sub.k].

Example 2: Let G: ([sigma],[mu]) be a fuzzy graph with [[mu].sub.*] = {[u.sub.1], [u.sub.2], [u.sub.3], [u.sub.4] , [u.sub.5]} and [[mu].sub.*] = {([u.sub.1],[u.sub.2]),([u.sub.2], [u.sub.3]),([u.sub.3], [u.sub.4]), ([u.sub.2],[u.sub.4]), ([u.sub.4],[u.sub.5])} with [mu] ([u.sub.2], = [mu] ([u.sub.3], [u.sub.4]) = 0.5, [mu] ([u.sub.1], [u.sub.2]) = [mu]([u.sub.4] , [u.sub.5]) = 1, [mu] ([u.sub.2],[u.sub.4]) = 0.3.

The various distance matrices associated with G are as follows,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Where [D.sub.g], [D.sub.[delta]], and [D.sub.[mu]] are the distance matrix of G with respect to the distances g, [delta], and [mu] respectively.

We illustrate the procedure for finding clusters of order k based on g-distance

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Since the matrix is symmetric we consider only the upper diagonal entries of Dg.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Clusters of order 1 (k=1 ):

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Now the maximal sets in the family {[C.sub.ilk]}, for i = 1,2,3,4,5 and l = 1,2,...5-i. are [C.sub.1] = ([u.sub.1],[u.sub.2]}, {[u.sub.2],[u.sub.3]}, {[u.sub.3],[u.sub.4]}, {[u.sub.4],[u.sub.5]}

Clusters of order 2 (k = 2)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

[C.sub.2] is the collection of maximal sets in the family {[C.sub.ilk]}, for i= 1,2,3and l = 1,2,...5-i.

[C.sub.2] = {[u.sub.1],[u.sub.2],[u.sub.3]},{[u.sub.2],[u.sub.3],[u.sub.4]},{[u.sub.3],[u.su b.4], [u.sub.5]}

Clusters of order 3 (k=3)

[R.sub.13] = ([u.sub.1], [u.sub.2], [u.sub.3], [u.sub.4]}, [R.sub.23] = {[u.sub.2], [u.sub.3], [u.sub.4], [u.sub.5]}, [R.sub.33] = {[u.sub.3], [u.sub.4], [u.sub.5]}, [R.sub.43] = {[u.sub.4], [u.sub.5]} and [R.sub.53] = {[u.sub.5] }

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

[C.sub.3] is the collection maximal sets in the family {[C.sub.ilh]}, for I = 1,2,3 and l = 1,2,...5-i.

[C.sub.3] = {[u.sub.1],[u.sub.2],[u.sub.3], [u.sub.1]}, {[u.sub.2],[u.sub.3], [u.sub.4],[u.sub.5]}

Clusters of order 5(k=5)

Clearly clusters of order 5 is the set [C.sub.5] = [u.sub.1]}, {[u.sub.2],[u.sub.3], [u.sub.4],[u.sub.5]}

This procedure can be applied to different distance matrices of a fuzzy graph and similar results can be obtained.

References

[1] A. Rosenfeld, Fuzzy graphs, In Fuzzy sets and their Applications to Cognitive and Decision Processes, (Zadeh. L.A., Fu, K.S., Shimura, M., Eds ;) Academic Press, New York (1975) 77-95.

[2] J.N. Mordeson, P.S. Nair, Fuzzy Graphs and Fuzzy Hypergraphs, Physica Verlag(2000).

[3] K. R. Bhutani, A Rosenfeld, Strong arcs in fuzzy graphs, Information Sci ences 152(2003) 319-322.

[4] K. R. Bhutani, A Rosenfeld,Geodesics in fuzzy graphs, Electronic Notes in Discrete Mathematics, 15(2003) 51-54.

[5] K, Sameena, M. S, Sunitha, Strong arcs and Maximum spanning trees in a fuzzy graph, International Journal of Mathematical Sciences, Volume 5,No 1 June(2006)17-20.

[6] K, Sameena, M. S, Sunitha, A characterization of g-self centered fuzzy graphs, The Journal of Fuzzy Mathematics, Volume 16, No.4, pp.787-791, (2008) (Los Angeles).

[7] K, Sameena, M. S, Sunitha, Fuzzy graphs in fuzzy neural netwoks, Proyeccious Journal of Mathematics, V-28, No.3, 239-252, 2009(Universidad Catolica del Norte- Chile).

[8] K, Sameena, M. S, Sunitha, On ss-paths and ss-distance in fuzzy graphs, Advances in Fuzzy Mathematics, V-5, No.1, 1-6, 2010.

[9] K, Sameena, M. S, Sunitha, On g-distance in fuzzy trees, The Journal of Fuzzy Mathematics, V-10, No.1, 2010, (Los Angeles).

[10] M. S. Sunitha, A. Vijayakumar, A characterization of fuzzy trees, Information Sciences 113 (1999) 293-300.

[11] M.S. Sunitha, A. Vijayakumar, Some metric aspects of fuzzy graphs, Proceedings of the Conference on Graph Connections, CUSAT(Eds.: R.Balakrishna, H.M.Mulder, A.Vijayakumar), Allied Publishers, New Delhi(1999)111- 114.

[12] M.S.Sunitha, A. Vijayakumar Complement of a fuzzy graph, Indian Journal of Pure and Applied Mathematics,33,() (2002)1451-1464,

[13] M. S. Sunitha, A. Vijayakumar, Blocks in fuzzy graphs, Journal of Fuzzy Mathematics,Vol.13,No.1 (2005)13-23.

Sameena K. (1) and M.S. Sunitha (2)

(1) Department of Mathematics, MES Mampad College, Malappuram-676 542, India

(2) Department of Mathematics, National Institute of Technology, Calicut-673 601, India. E-mail: sameenakalathodi@gmail.com, sunitha@nitc.ac.in