Identification of fuzzy blocks using sum distance metric

Abstract

— In this paper, new concepts are introduced to enhance the process of block identification in fuzzy graphs using sum distance metric and special type of cycles, which is called a strongest strong cycle, locamin cycle. An Algorithm is developed for retrieving information from Big-Data using block identification.

Keywords

Sum distance metric strongest strong cycle (SSC)Big-Data

1 Introduction

Fuzzy graph theory was introduced by Azriel Rosenfeld [19] in 1975. Fuzzy graph theory is now finding numerous applications in modern science and technology especially in the fields of neural networks, expert systems, information theory, cluster analysis, medical diagnosis, control theory, etc. Rosenfeld [19] has obtained the fuzzy graph-theoretic concepts like bridges, paths, cycles, trees and connectedness and established some of their properties. Fuzzy Blocks were characterized by Sunitha and Vijaykumar [14]. Bhutani et al. introduced the concepts of strong arcs, fuzzy end nodes [6 –8]. Concepts of m-polar fuzzy graph was discussed in [9]. Mathew and Sunitha identified different types of arcs in a fuzzy graph [13]. Sum Distance Metric was introduced by Tom and Sunitha [25].

Mathew and Sunitha [15] introduced a new connectivity parameter called cycle connectivity which is a new type of cycle called a strongest strong cycle (SSC), and a new subclass of fuzzy graphs called θ-fuzzy graphs. In this paper, we present characterization of blocks using Sum distance metric. Preliminaries required to derive the results of this paper are given in Section 2. Relation between arcs and strongest path using Sum distance metric is discussed in section 3. The concept of the SSC, locamin cycle, fuzzy blocks and their relationship with strongest path using sum distance metric and strength of connectedness is discussed in section 4, θ-fuzzy graph is characterized in section 5.

Big challenge in the business environment is combining structured and unstructured formats from various applications and projects into single format. Big Data handles this kind of data and provides valuable insights.

In the section 6, 7 we provide an algorithm and application in big data to find out blocks which are groups of similar data or cluster using Sum distance metric and strength of connectedness was given.

2 Preliminaries

First, we recollect some basic ideas from undirected graphs [16]. Recall that a crisp graph is an ordered pair G = (V, E)where V is the set of vertices of G, and E is the set of edges of G.

A fuzzy graph (f-graph) is a triplet G : (V, σ, μ), where σ is a fuzzy subset of a set V and μ is a fuzzy relation on σ. It is assumed that V is finite and nonempty, and μ is reflexive and symmetric. Thus, if G : (V, σ, μ) is a fuzzy graph, then σ : V → [0, 1], and μ : V × V → [0, 1] is such that μ (u, v) ≤ σ (u) ∧ σ (v) , for all u, b ∈ V, where ∧ denotes the minimum. We denote the underlying graph of a fuzzy graph G : (V, σ, μ) by G^* : (V, σ^*, μ^*), where σ * = {u ∈ V : σ (u) >0} and μ * = {(u, v) ∈ V × V : μ (u, v) >0}. In examples, if σ is not specified, it is chosen suitably. In addition, G : (V, σ, μ) is called a trivial fuzzy graph if G^* : (V, σ^*, μ^*) is trivial. That is, σ^* is a singleton set. In a fuzzy graph G : (V, σ, μ), a path P of length n is a sequence of distinct nodes u₀, u₁, . . . , u_n such that μ (u_i-1, u_i) >0, i = 1, 2, …, n and the degree of membership of a weakest arc is defined as its strength. If u₀ = u_n, and n ≥ 3, then P is called a cycle and a cycle P is called a fuzzy cycle (f-cycle) if it contains more than one weakest arc. A single node is considered as a trivial path of length 0.

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_G (x, y). An xy path P is called a strongest xy path if its strength equals CONN_G (x, y). An f-graph G : (V, σ, μ) is connected if for every x, y in σ^*, CONN_G (x, y) > 0. If G is disconnected, maximal connected fuzzy subgraphs are called components. Clearly, if G is connected, then any two nodes are joined by a path. An arc (u, v) is a fuzzy bridge of G : (V, σ, μ) if the deletion of (u, v) reduces the strength of connectedness between some pair of nodes. Equivalently, (u, v) is a fuzzy bridge if and only if there are nodes x, y such that (u, v) is an arc of every strongest x-y path. Note that the strength of connectedness between any different pairs of nodes in a connected graph is 1, whereas in a connected fuzzy graph, it can be any real number in (0, 1].

In [8], Bhutani and Rosenfield introduced the concept of a strong arc and a strong path as given. An arc (u, v) in G is called α-strong, if μ (u, v) > CONN_G-(u,v) (u, v). An arc (u, v) in G is called β-strong, if μ (u, v) > CONN_G-(u,v) (u, v). An arc (u, v) in G is called α-arc,if μ (u, v) > CONN_G-(u,v) (u, v) A δ-arc (u, v) is called a δ*-arc if μ(u, v)> μ(x, y) where (x, y) is a weakest arc of G.

A strong arc is either α-strong or β-strong by [13]. A subgraph of a graph G = (V, E) is a graph H = (W, F), where W ⊆ V and F ⊆ E. A simple graph is an undirected graph that has no loops (edges starting and ending at the same vertex) and not more than one edge between any two different vertices. A simple graph with a single node is called a trivial graph, and the one with no edges is referred as an empty graph. Two vertices x and y in an undirected graph G are said to be adjacent in G if (x, y) is an edge of G. An edge may be also represented as xy or yx. The set of all vertices adjacent to a vertex x in G is called the neighbor set ofx, which is denoted by N(x). A graph G is called connected if there is a path joining any two nodes in G. A graph G is called a tree if it is connected and acyclic. The number of connected components in G is denoted by ω (G). A vertex v of G is said to be a cut vertex of G if ω (G - {v}) > ω (G) or G - {V} is trivial. Similarly, an edge e of G is called a cut edge if ω (G - {e}) > ω (G) or G - {e} is empty. G is said to be a complete graph if all the vertices in G are pairwise adjacent.

2.1 Basic definitions and results in fuzzy graphtheory

Definition 1. [25] Let G: (V, σ, μ) be a connected fuzzy graph. For any path P:u₀ - u₁ - u₂ . . . - u_n, length of P is defined as the sum of the weights of the arcs in P. $L (P) = \sum_{i = 1}^{n} μ (u_{i - 1}, u_{i})$ . If n = 0, define L (P) =0 and for n ≥ 1, L (P) >0. For any two nodes u, v in G, let P = {P_i : Piis au - vpath, i = 1, 2, 3 . . .}. The sum distance between u and v is defined as $d_{s} (u, v) = min {L (P_{i}) : P_{i} \in P, i = 1, 2, 3 . . .}$

Note that, Sum distance in a fuzzy graph is a Metric.

Definition 2. [13] A fuzzy graph is said to be a block (also called non- separable) if it is connected and has no fuzzy cutnodes.

Note that in a graph, a block cannot have bridges. However, in fuzzy graphs, a block may have fuzzy bridges.

Next theorem is the first characterization of blocks in fuzzy graphs due to Sunitha and Vijaykumar. The authors use strongest paths to characterize blocks.

Theorem 1. [ 14] The following statements are equivalent for a connected fuzzy graph G : (V, σ, μ)

G is a block.

Any two nodes u and v such that (u, v) is not a fuzzy bridge are joined by two internally disjoint strongest paths.

For every three distinct nodes of G, there is a strongest path joining any two of them not containing the third.

When the fuzzy graph is arc disjoint, the blocks can be easily characterized as in the following theorem as given by Mathew and Sunitha [15].

Definition 3. [15] A cycle C is called a strong cycle if all arcs of C are strong. It is called a locamin cycle if every node of the cycle lies on a weakest arc.

Definition 4. [15] A fuzzy graph G : (V, σ, μ) is called arc disjoint if no two cycles share a common arc. Now, we have a theorem related to blocks in arc disjoint fuzzy graphs.

Theorem 2. [15] A connected arc disjoint fuzzy graph G : (V, σ, μ) with at least three arcs is non-separable if and only if any two adjacent arcs lie on a locamin cycle.

Remark 1. [15] There are no α-arcs in a fuzzy cycle. For, if (u, v) is a α-arc in G, then it becomes the unique weakest arc of G, which contradicts that G is a fuzzy cycle. Also, a fuzzy cycle cannot have all its arcs α-strong.

Theorem 3. [15] Let G : (V, σ, μ) be fuzzy Graph such that G*is a cycle. Then G is a fuzzy cycle iff G has at least two β-strong arcs.

When the underlying structure of a fuzzy graph is a cycle, we can see that it will be a block only when it is strong and when it is the union of different strongest paths. Motivated, by this Mathew and Sunitha [15] introduced the concept of Strongest Strong Cycle.

Definition 5. [15] The strength of a cycle C in an f-graph is defined as the weight of a weakest arc in C.

Definition 6. [15] A cycle C in an fuzzy graph G is called an SSC if C is the union of two strongest strong u-v paths for every pair of nodes u and v in C, except when (u, v) is an f-bridge of G in C.

Theorem 4. [ 15] Let G : (V, σ, μ) be fuzzy graph such that G^* is a cycle. Then, the following are equivalent.

G is a block.

G is an SSC.

G is a locamin cycle.

Theorem 5. [ 15] Let G : (V, σ, μ) be an arc disjoint fuzzy graph with at least three nodes. Then, the following are equivalent.

G is a block.

G is an SSC.

G is a locamin cycle.

Definition 7. [15] Let G : (V, σ, μ) be fuzzy graph. Then, for any two nodes u and v of G, there associated a set say θ (u, v) called the θ-evaluation of u and v and is defined as θ (u, v) = {α : α ∈ (0, 1]}, where α is the strength of a strong cycle passing through both u and v.

Definition 8. [15] Max {α : α ∈ θ (u, v) ; u, v ∈ σ^*} is defined as the cycle connectivity between u and v in G : (V, σ, μ) and is denoted by $C_{u, v}^{G}$ . If (u, v) = φ, for some pair of nodes u and v, we define the cycle connectivity between u and v to be 0.

Definition 9. [15] Le(V, σ, μ) be fuzzy graph. G is said to be a θ-fuzzy graph if θ-evaluation of each pair of nodes in G is either empty or a singleton set. In other words, G is called a θ-fuzzy graph if for each pair of nodes u and v, either there is no strong cycle passing through u and v or all strong cycles passing through u and v have the same strength.

The following are a set of necessary conditions for a fuzzy graph to be a block.

Theorem 6. [ 15] If G : (V, σ, μ) is a block, then the following conditions hold and are equivalent.

Every two nodes of G lie on a common strong cycle.

Each node and a strong arc of G lie on a common strong cycle.

Any two strong arcs of G lie on a common strong cycle.

For any two given nodes and a strong arc in G, there exists a strong path joining the nodes containing the arc.

For every three distinct nodes of G, there exist strong paths joining any two of them containing the third.

For every three nodes of G, there exist strong paths joining any two of them which does not contain the third.

Proposition 2. [15] Arc disjoint fuzzy graphs are θ-fuzzy graphs.

Theorem 7. [ 15] Let G : (V, σ, μ) be a θ-fuzzy graph. Then, the following statements are equivalent.

G is a block.

Every two nodes of G lie on a common SSC.

Each node and a strong arc of G lie on a common SSC.

Any two strong arcs of G lie on a common SSC.

For any two given nodes u and v such that (u, v) is not a fuzzy bridge and a strong arc (x, y) in G, there exists a strongest strong u-v path containing the arc (x, y).

For every three distinct nodes, u_ii = 1, 2, 3 of G such that (u_i, u_j) , i ≠ j is not a fuzzy bridge, there exist strongest strong paths joining any two of them containing the third.

For every three distinct nodes u_ii = 1, 2, 3 of G such that (u_i, u_j) , i ≠ j is not a fuzzy bridge, there exist strongest strong paths joining any two of them not containing the third.

In the following section, we establish the relationship between Sum distance metric and strength of connectedness in different types of arcs. In all examples, the membership value of a node is taken as 1, for simplicity; therefore, it will not be displayed in diagrams

3 Relationship between arcs and strongest path using sum distance metric

Lemma 3.1. Let G : (V, σ, μ) be fuzzy graph. If (u, v) is an α-arc such. that d_s (u, v) > CONN_G-(u,v) (u, v), then there is a strongest pathp. Also, if

L (P) > μ (u, v),then d_s (u, v) = μ (u, v)

L (P) < μ (u, v), then d_s (u, v) = L (p)

L (P) = μ (u, v), then d_s (u, v) = L (P) = μ (u, v)

Proof. Let (u, v) be α-arc.

Then,μ (u, v) > CONN_G-(u,v) (u, v).

By [13], there exist a strongest path. Let it be P. We need to prove,d_s (u, v) = μ (u, v) $L (P) = \sum_{i = 1}^{n} μ (u_{i - 1}, u_{i}) = {CONN}_{G - (u, v)} (u, v) + k$ (1)

Where k is sum of arc weight of other arcs in the path P.

Also,μ (u, v) > CONN_G-(u,v) (u, v). $μ (u, v) = {CONN}_{G - (u, v)} (u, v) + j$ (2)

L(P) – μ (u, v) = k–j, by Equations (1) and (2)

L (P) > μ (u, v)

Then, k - j > 0

By definition, Sum distance metric,d_s (u, v) = min {L (P) : P_i ∈ P, i = 1, 2, 3 . . .}

Therefore, d_s (u, v) = μ (u, v)

L (P) < μ (u, v)

Then this strongest path has minimum length than membership value of arc(u, v).

Thus, d_s (u, v) = L (P)

L (P) = μ (u, v)

Thus, again by definition of Sum distance metric, d_s (u, v) = min {L (P_i) : P_i ∈ P, i = 1, 2, 3 . . .}

Therefore, d_s (u, v) = μ (u, v) Hence the proof.□

Example 1. In Fig. 1, d_s (u, v) = μ (u, v) = min(0.6, 1.3, 1.1, 1.2) =0.6

Fig.1

Fuzzy graph with strongest path.

${CONN}_{G - (u, v)} (u, v) = sup (0.3, 0.2, 0.4) = 0.4$

Thus, d_s (u, v) > CONN_G-(u,v) (u, v) and there is a strongest u-v path u-x-y-v and also d_s (u, v) = μ (u, v)

Lemma 3.2. Let (V, σ, μ) be fuzzy graph. If d_s (u, v) > CONN_G-(u,v) (u, v) and there is a strongest path such that d_s (u, v) = μ (u, v) then (u, v) is α-arc.

Proof. Given, d_s (u, v) > CONN_G-(u,v) (u, v) $d_{s} (u, v) = {CONN}_{G - (u, v)} (u, v) + k, k > 0$ (3) $Also, d_{s} (u, v) = μ (u, v) .$ (4)

From Equations (3), (4), μ (u, v) = CONN_G-(u,v)(u, v) + k.

This implies, μ (u, v) = CONN_G-(u,v) (u, v)

Thus, by definition, (u, v) is α-arc. Hence the proof.□

Lemma 3.3 Let G : (V, σ, μ) be fuzzy graph. If (u, v) be α-arc and d_s (u, v) < CONN_G-(u,v) (u, v) then there is a u-v path P which is not strongest and d_s (u, v) = L (P).

Proof. Given (u, v) is α-arc.

Therefore, $μ (u, v) > {CONN}_{G - (u, v)} (u, v) > d_{s} (u, v)$ (5)

By definition, Sum distance metric, d_s (u, v) = min L (P), where P is the u-v path in G.

And L (P) = $L (P) = \sum_{i = 1}^{n} μ (u_{i - 1}, u_{i})$

By Equation (5), there exist u-v path whose sum distance is less than μ (u, v)

Since a path other than arc (u, v) should contain at least two arcs, there exist a path in which membership value of at least one arc is strictly less than μ (u, v), Also, d_s (u, v) < CONN_G-(u,v) (u, v) < μ (u, v)

This proves that this path is not strongest.

Example 2. In Fig. 2, d_s (u, v) = min(0.2, 0.6, 1.3) =0.2 ${CONN}_{G - (u, v)} (u, v) = sup (0.1, 0.4) = 0.4$

Fig.2

Fuzzy graph with α-arc.

Here, d_s (u, v) < CONN_G-(u,v) (u, v).

u-x-v path is not strongest path.

Lemma 3.4 Let G : (V, σ, μ) be fuzzy graph. (u, v) is β-arc and d_s (u, v) = CONN_G-(u,v) (u, v) iff there is at least a strongest path such that d_s (u, v) = μ (u, v).

Proof. Given (u, v) is β-arc.

Then, $μ (u, v) = {CONN}_{G - (u, v)} (u, v)$ (6)

By definition of β-arc, there is a strongest path such that membership value of each arc is at least CONN_G-(u,v) (u, v) Thus, by definition of Sum distance metric, $d_{s} (u, v) = min L (P) = {CONN}_{G - (u, v)} (u, v) = μ (u, v)$ by Equation (6).

Hence the proof.□

Conversely, let there be a strongest path such that d_s (u, v) = μ (u, v).

Since the path is strongest, strength of this path is equal to CONN_G-(u,v) (u, v).

Thus, membership value of any arc in this path is at least CONN_G-(u,v) (u, v)

Therefore, any strongest path in G - (u, v), will have length greater than CONN_G-(u,v) (u, v) and hence d_s (u, v) = μ (u, v).

By assumption, d_s (u, v) = CONN_G-(u,v) (u, v)

Thus, μ (u, v) = CONN_G-(u,v) (u, v) and hence arc (u, v) is β-arc.

Example 3. In Fig. 3, (u, v) is β-arc. $d_{s} (u, v) = min (. 6, . 9, . 8, 3.4) = . 6$ ${CONN}_{G - (u, v)} (u, v) = sup (. 4, . 2, . 6) = . 6$

Fig.3

Fuzzy graph with β-arc.

There is a strongest u-v path u-w-x-y-z-v and d_s (u, v) = μ (u, v)

Lemma 3.5 Let G : (V, σ, μ) be fuzzy Graph. If (u, v) be β-arc and d_s (u, v) < CONN_G-(u,v) (u, v)then there is at least a path which is not strongest and membership value of each arc of this path is less than CONN_G-(u,v) (u, v).

Proof. Given, (u, v) is β-arc.

Then, μ (u, v) = CONN_G-(u,v) (u, v)

Also, d_s (u, v) < CONNA_G-(u,v) (u, v) = μ (u, v)

Thus, d_s (u, v) < μ (u, v)

By definition of Sum distance metric, there exist a u-v path such that membership value of each arc in this path is strictly less than CONN_G-(u,v) (u, v) and also the path P is not strongest.□

Example 4. In Fig. 4, $d_{s} (u, v) = min (. 4, . 2, 1.3) = . 2$ ${CONN}_{G - (u, v)} (u, v) = sup (. 1, . 4) = . 4$

Fig.4

Fuzzy graph with β-arc.

There is a path u-x-v which is not strongest.

Lemma 3.6 Let G : (V, σ, μ) be fuzzy graph and if (u, v) is α-arc, then d_s (u, v) < CONN_G-(u,v) (u, v) and d_s (u, v) = μ (u, v) Also, there is a strongest path in G-(u,v).

Proof. Let (u, v) be α-arc.

Then, (u, v) is unique weakest arc of at least one cycle in G.

This implies, every u-v path has strength greater than CONN_G-(u,v) (u, v). Thus there exist a strongest u-v path.

By definition, $μ (u, v) = {CONN}_{G - (u, v)} (u, v)$ (7)

By definition of Sum distance metric, $d_{s} (u, v) = min L (P) = μ (u, v)$ (8)

By Equations (7) and (8), d_s (u, v) < CONN_G-(u,v) (u, v).□

Lemma 3.7. Let G : (V, σ, μ) be fuzzy graph. If there is a strongest u-v path such that d_s (u, v) ≥ CONN_G-(u,v) (u, v),then (u, v) is either α-arc or β-arc.

Proof. Let P be strongest u-v path in G.

Therefore, strength of path $P = {CONN}_{G - (u, v)} (u, v) = kP = {CONN}_{G - (u, v)} (u, v)$ (9)

The membership value of arcs of this path is greater than or equal to k (say). d_s (u, v) cannot be greater than μ (u, v),by definition of Sum distance metric. Thus, we have d_s (u, v) ≤ μ (u, v).

d_s (u, v) = μ (u, v)

μ (u, v) = d_s (u, v) ≥ CONN_G-(u,v) (u, v) by assumption.

This implies arc (u, v) is either α-arc or β-arc.

d_s (u, v) < μ (u, v).This implies there is a path whose length is strictly less than μ (u, v)

By assumption, d_s (u, v) ≥ CONN_G-(u,v)(u, v), this path is not strongest. Hence the proof.□

4 Characterization of SSC, Locamin cycle, blocks using sum distance metric

Bhutani and Rosenfeld [8] introduced the concept of locamin cycle to characterize blocks in arc-disjoint fuzzy graph. Here, we characterize SSC, locamin cycle and fuzzy blocks using Sum distance metric.

Theorem 4.1 Let G : (V, σ, μ) be fuzzy graph, G is an SSC iff d_s (u, v) ≥ CONN_G-(u,v) (u, v),forevery strong arc in G.

Proof. Let G : (V, σ, μ) be fuzzy graph and it is an SSC.

Since, G is an SSC and every path must be strongest and strong.

Therefore, by lemma 3.1, 3.2, 3.4, d_s (u, v) ≥ CONN_G-(u,v) (u, v),for every arc in G.

The converse of the theorem follows from lemma 3.7

Hence the proof.□

Theorem 4.2 Let G : (V, σ, μ) be fuzzy graph such that G^* is a cycle, then G is an locamin cycle iff d_s (u, v) ≥ CONN_G-(u,v) (u, v),for every arc in G.

Proof. Assume G is an locamin cycle, where G^*is a cycle.

By theorem 4 [15], G is an SSC.

Therefore, all cycles are strongest strong.

Thus, by lemma 3.1, 3.4, d_s (u, v) ≥ CONN_G-(u,v) (u, v).

Conversely, Assume d_s (u, v) ≥ CONN_G-(u,v) (u, v) in G.

Since the underlying Crisp graph is cycle and by theorem 4.1, G is an SSC. If possible, suppose that G is not locamin. Then, there exists some node w such that w is not on a weakest arc of G. Let (u, w) and (w, v) be the two arcs incident on w, which are not weakest arcs. This implies that the path u-w-v is the unique strongest u-v path in G, which is in contradiction to the assumption that G is an SSC.□

Example 1. In Fig. 5, C: a-b-c-d is an SSC and, locamin cycle. It can be observed that d_s (u, v) ≥ CONN_G-(u,v) (u, v),for every arc in G.

Fig.5

SSC and locamin cycle.

When the underlying structure is a cycle, we can see that the concepts of SSC and locamin cycle are equivalent and become a block. Hence, we have the following.

Theorem 4.3 Let G : (V, σ, μ) be an arc disjoint fuzzy graph with at least three nodes. G is a block iff d_s (u, v) ≥ CONN_G-(u,v) (u, v),for every arc in G.

Proof. Assume G is a block.

By theorem 5 [15], G is an SSC.

By theorem 1, the result follows.□

5 Characterization of blocks in θ-fuzzy graph using Sum distance metric

According to Mathew and Sunitha [15], in a θ-fuzzy graph which is a block, the concepts of strong path and strongest path coincide, and thus, the concepts of strong cycle and SSC are also equivalent.

Theorem 5.1. Let G : (V, σ, μ) be a θ-fuzzy graph. Then, G is a block iff d_s (u, v) ≥ CONN_G-(u,v) (u, v), for every arc in G.

Proof. Suppose, G is a block.

Then by theorem 5 [15], there is an SSC.

And, it is a θ-fuzzy graph. Therefore, for each pair of nodes u and v, either there is no strong cycle passing through u and v or all strong cycles passing through u and v have the same strength. Thus, there exist α-arc or β-arc and all the paths are strong.

By Lemma 1, 2, 4 d_s (u, v) ≥ CONN_G-(u,v) (u, v), for every arc in G.

Conversely, Assume d_s (u, v) ≥ CONN_G-(u,v) (u, v), for every arc in G.

By theorem 3, G is a block.□

Example 1. In Fig. 6, d_s (u, v) ≥ CONN_G-(u,v) (u, v), for every arc in the θ-fuzzy graph G.

Fig.6

θ-fuzzy graph.

6 Algorithm for block identification using sum distance metric and strength of connectedness

Let G : (V, σ, μ) be a fuzzy graph. Then the algorithm to find blocks using Sum distance metric is given by the following steps.

Calculate strength of connectedness of each arc in the graph G.

Let H_k be the collection of arcs having same strength of connectedness k and d_s (u, v) ≥ CONN_G-(u,v) (u, v)in G, for every arc which are adjacent to each other.

Required Block or cluster is given by

C_{k} = {\begin{matrix} u \in H_{k} ∖ d_{s} (u, v) \geq {CONN}_{G - (u, v)} (u, v) and \\ {CONN}_{G - (u, v)} (u, v) = {CONN}_{G - (v, w)} (u, w), \\ \forall adjacent arc in H_{k} \end{matrix}

The complexity in calculating strength of connectedness between every pair of vertices is O (n²) as given in [4]. Also, in calculating sum distance, the time complexity is O (n²) according to [18], where n denotes the number of vertices in the fuzzy graph. Since the above algorithm calculates strength of connectedness and sum distance between every pair of vertices the time complexity is O (n²).

7 Application of block identification using sum distance metric and strength of connectedness in Big-Data

Big data is always being generated by everything around us. Every digital process and social media exchange produces it. Systems, sensors and mobile devices transmit it. Big data is arriving from multiple sources at an alarming velocity, volume and variety. To extract meaningful value from big data, you need optimal processing power, analytics capabilities and skills.

Hadoop is an open-source software framework for storing big- data and running applications on clusters of commodity hardware. It provides massive storage for any kind of data, enormous processing power and the ability to handle virtually limitless concurrent tasks or jobs.

We design an algorithm to retrieve information of similar data from servers represented as nodes using sum distance metric and strength of connectedness

In Fig. 7, we represent fuzzy graph model. Let nodes a, b, c, d represent data related to particular format and e, f, g, h of another. The membership value of similar data is same, but the interconnecting arc has different membership value.

Fig.7

Fuzzy graph model.

In Fig. 7, the strength of connectedness of all arcs in a, b, c, d is 0.6 and e, f, g, h is 0.4.

$H_{0.6} = {(a, b), (b, d), (c, d), (a, c)}$ $H_{0.4} = {(e, f), (f, h), (h, g), (g, e)}$

Also, d_s (u, v) ≥ CONN_G-(u,v) (u, v), for every adjacent arc in H_0.6 and H_0.4 but interconnecting arcs (b. e), (d, g) have different strength of connectedness.

a, b, c, d, e, f, g, h were the clusters formed by above algorithm.

8 Conclusion

The identification and extraction of blocks in graphs is widely used in many areas of science and technology, including chemistry, communication networks, clustering and Big-Data analysis. In this paper, relationship between Sum distance metric and strength of connectedness in types of arcs, locamin cycle, SSC, θ-fuzzy graph is discussed. In addition, an algorithm and application to sort data in Big-Data analytics through block identification is presented. This work can be further extended to different type of fuzzy graphs such as (1) m-polar fuzzy graphs (2) intuitionistic fuzzy graphs (3) interval valued fuzzy graphs.

References

Akram

, Karunambigai

M.G.

, Metric in bipolar fuzzy graphs, World Appl. Sci. J. 14(12) (2011), 1920–1927.

Akram

, Dudek

W.A.

, Regular bipolar fuzzy graphs, Neural Comput. Appl 21 (2012), 197–205.

Akram

, Interval-valued fuzzy line graphs, Neural Comput. Appl 21 (2012), 145–150.

Banerjee , Saibal , An optimal algorithm to find the degrees of connectedness in an undirected edge-weighted graph, Pattern Recognition Letters 12 (1991), 421–424.

Bhattacharya

, Suraweera

, An algorithm to compute the max-min powers and a property of fuzzy graphs, Pattern Recognit. Lett. 12 (1991), 413–420.

Bhutani

K.R.

, and Rosenfeld

, Fuzzy end nodes in fuzzy graphs, Inf. Sci. 152 (2003), 323–326.

Bhutani

K.R.

, On automorphisms of fuzzy graphs, Pattern Recognit. Lett. 9 (1989), 159–162.

Bhutani

K.R.

, and Rosenfeld

, Strong arcs in fuzzy graphs, Inf. Sci. 152 (2003), 319–322.

Ghorai

, and Pal , Madhumangal , On degrees of m-polar fuzzy graphs with application, Journal of Uncertain Systems 11 (2017), 294–305.

10.

Harary

, Graph Theory, 3rd ed. Reading, MA, USA: Addison-Wesley, 1972.

11.

Mathew

, Anjali

, On blocks and stars in fuzzy graphs, Journal of Intelligent & Fuzzy Systems 28 (2015), 1659–1665.

12.

Mathew

, Sunitha

M.S.

, Bonds in graphs and fuzzy graphs, Adv. Fuzzy Sets Syst. 6(2) (2010), 107–119.

13.

Mathew

, Sunitha

M.S.

, Types of arcs in a fuzzy graph, Inf. Sci. 179(11) (2009), 1760–1768.

14.

Mathew

, Sunitha

M.S.

, A characterization of blocks in fuzzy graphs, J. Fuzzy Math. 19(1) (2011), 999–1006.

15.

Mathew

, Sunitha

M.S.

, Strongest strong cycles and θ-fuzzy graphs, IEEE Transactions on Fuzzy Systems 21(6) (2013), 1096–1104.

16.

Mordeson

J.N.

, Nair

P.S.

, Arc disjoint fuzzy graphs, in Proc. 18th Int. Conf. North Amer. Fuzzy Inf. Process. Soc., 1999, pp. 65–69.

17.

Mordeson

J.N.

, Nair

P.S.

, Fuzzy Graphs and Fuzzy Hypergraphs New York, NY, USA: Physica-Verlag, 2000.

18.

Sarwar

, Akram

, An algorithm for computing certain metrics in intuitionistic fuzzy graphs, Journal of Intelligent & Fuzzy Systems 30 (2016), 2405–2416.

19.

Rosenfeld

, Fuzzy graphs, Fuzzy Sets and Their Applications to Cognitive and Decision Processes. Zadeh

L.A.

et al., Eds., New York, NY, USA, Academic, 1975, pp. 77–95 .

20.

Sunitha

M.S.

, Vijayakumar

, A characterization of fuzzy trees, Inf. Sci. 113 (1999), 293–300.

21.

Sunitha

M.S.

, Vijayakumar

, Some metric aspects of fuzzy graphs, in Proc. Conf. Graph Connect, 1999, pp. 111–114.

22.

Sunitha

M.S.

, Vijayakumar

, Complement of a fuzzy graph, Indian J. Pure Appl. Math 33(9) (2002), 1451–1464.

23.

Sunitha

M.S.

, Vijayakumar

, Blocks in fuzzy graphs, J. Fuzzy Math 13(1) (2005), 13–23.

24.

Pandey

, Tokekar

, Prominence of MapReduce in BIG DATA Processing. In Fourth International Conference on Communication Systems and Network Technologies, IEEE, 2014, pp. 555–560.

25.

Tom

, Sunitha

, Sum distance in fuzzy graphs, Annals of Pure and Applied Mathematics 7(2) (2014), 73–89.

26.

Tong

, Zheng

, An algorithm for finding the connectedness matrix of a fuzzy graph, Congr. Numer. 120 (1996), 189–192.

27.

Yeh

R.T.

, Bang

S.Y.

, Fuzzy relations, fuzzy graphs and their applications to clustering analysis, Fuzzy Sets and Their Applications. Zadeh

L.A.

, et al., Eds., New York, NY, USA Academic, 1975, pp. 125–149 .

28.

Zadeh

L.A.

, Fuzzy sets, Inf. Comput 8 (1965), 338–353.