A Novel Weighted Distance Measure for Multi-Attributed Graph
Muhammad Abulaish, SMIEEE

Jahiruddin∗

Department of Computer Science
South Asian University
New Delhi-21, India
abulaish@sau.ac.in

Department of Computer Science
Jamia Millia Islamia
New Delhi-25, India
jahir.jmi@gmail.com

arXiv:1801.07150v1 [cs.SI] 22 Jan 2018

ABSTRACT
Due to exponential growth of complex data, graph structure has
become increasingly important to model various entities and their
interactions, with many interesting applications including, bioinformatics, social network analysis, etc. Depending on the complexity of the data, the underlying graph model can be a simple
directed/undirected and/or weighted/un-weighted graph to a complex graph (aka multi-attributed graph) where vertices and edges are
labelled with multi-dimensional vectors. In this paper, we present
a novel weighted distance measure based on weighted Euclidean
norm which is defined as a function of both vertex and edge attributes, and it can be used for various graph analysis tasks including classification and cluster analysis. The proposed distance
measure has flexibility to increase/decrease the weightage of edge
labels while calculating the distance between vertex-pairs. We have
also proposed a MAGDist algorithm, which reads multi-attributed
graph stored in CSV files containing the list of vertex vectors and
edge vectors, and calculates the distance between each vertex-pair
using the proposed weighted distance measure. Finally, we have
proposed a multi-attributed similarity graph generation algorithm,
MAGSim, which reads the output of MAGDist algorithm and generates a similarity graph that can be analysed using classification
and clustering algorithms. The significance and accuracy of the
proposed distance measure and algorithms is evaluated on Iris and
Twitter data sets, and it is found that the similarity graph generated
by our proposed method yields better clustering results than the
existing similarity graph generation methods.

CCS CONCEPTS
• Information systems → Similarity measures; Data analytics; Clustering; • Human-centered computing → Social network
analysis;

KEYWORDS
Data mining, Clustering, Multi-attributed graph, Weighted distance
measure, Similarity measure
∗ To

whom correspondence should be made

Permission to make digital or hard copies of all or part of this work for personal or
classroom use is granted without fee provided that copies are not made or distributed
for profit or commercial advantage and that copies bear this notice and the full citation
on the first page. Copyrights for components of this work owned by others than ACM
must be honored. Abstracting with credit is permitted. To copy otherwise, or republish,
to post on servers or to redistribute to lists, requires prior specific permission and/or a
fee. Request permissions from permissions@acm.org.
Compute ’17, Bhopal, India
© 2017 ACM. 978-1-4503-5323-6/17/11. . . $15.00
DOI: 10.1145/3140107.3140114

ACM Reference format:
Muhammad Abulaish, SMIEEE and Jahiruddin. 2017. A Novel Weighted
Distance Measure for Multi-Attributed Graph. In Proceedings of 10th Annual ACM India Compute Conference, Bhopal, India, November 16–18, 2017
(Compute ’17), 9 pages.
DOI: 10.1145/3140107.3140114

1

INTRODUCTION

Due to increasing popularity of Internet and Web2.0, the UserGenerated Contents (UGCs) are growing exponentially. Since most
of the UGCs are not independent, rather linked, the graph data structure is being considered as a suitable mathematical tool to model
the inherent relationships among data. Simple linked data are generally modelled using simple graph G = (V , E), where V is the set
of vertices representing key concepts or entities and E ⊆ V × V is
the set of links between the vertices representing the relationships
between the concepts or entities. Depending on the nature of data
to be modelled, the graph G could be weighted/un-weighted or
directed/undirected, and it may have self-loops. However, there are
many complex data like online social networks, where an entity is
characterized by a set of features and multiple relationships exist
between an entity-pair. To model such data, the concept of multiattributed graph can be used wherein each vertex is represented by
an n-dimensional vector and there may be multiple weighted edges
between each pair of vertices. In other words, in a multi-attributed
graph, both vertices and edges are assigned multiple labels. One of
the important tasks related to graph data analysis is to decompose
a given graph into multiple cohesive sub-graphs, called clusters,
based on some common properties. The clustering is an unsupervised learning process to identify the underlying structure (in the
form of clusters) of data, which is generally based on some similarity/distance measures between data elements. Graph clustering
is special case of clustering process which divides an input graph
into a number of connected components (sub-graphs) such that
intra-component edges are maximum and inter-components edges
are minimum. Each connected component is called a cluster (aka
community) [13]. Though graph clustering has received attention
of many researchers and a number of methods for graph clustering
has been proposed by various researchers [19], to the best of our
knowledge, the field of clustering multi-attributed graph is still
unexplored.
Since similarity/distance measure is the key requirement for
any clustering algorithm, in this paper, we have proposed a novel
weighted distance measure based on weighted Euclidean norm to
calculate the distance between the vertices of a multi-attributed
graph. The proposed distance measure considers both vertex and
edge weight-vectors, and it is flexible enough to assign different
weightage to different edges and scale the overall edge-weight

Compute ’17, November 16–18, 2017, Bhopal, India
while computing the weighted distance between a vertex-pair. We
have also proposed a MAGDist algorithm that reads the lists of
vertex and edge vectors as two separate CSV files and calculates the
distance between each vertex-pairs using the proposed weighted
distance measure. Finally, we have proposed a multi-attributed similarity graph generation algorithm, MAGSim, which reads the output
of MAGDist algorithm and generates a similarity graph. In other
words, MAGDist and MAGSim algorithms can be used to transform
a multi-attributed graph into a simple weighted similarity graph,
wherein a single weighted edge exists between each vertex-pair.
Thereafter, the weighted similarity graph can be analysed using
existing classification and clustering algorithms for varied purposes.
The efficacy of the proposed distance measure and algorithms is
tested over the well-known Iris data set and a Twitter data set
related to three different events. The proposed similarity graph generation approach is compared with other existing similarity graph
generation methods like Gaussian kernel and k-nearest neighbours
methods, and it is found that our proposed approach yields better
clustering results in comparison to the existing methods. Moreover,
the proposed distance measure can be applied to any graph data
where both vertices are edges are multi-dimensional real vectors.
In case, the data is not linked, i.e., edges do not exist between the
edges, the proposed distance measure simple works as an Euclidean
distance between the node vectors.
The rest of the paper is organized as follows. Section 2 presents
a brief review on various distance measures and graph clustering methods. Section 3 presents the formulation of our proposed
weighted distance measure for multi-attributed graph. It also presents
the founding mathematical concepts and formal descriptions of the
MAGDist and MAGSim algorithms. Section 4 presents the experimental setup and evaluation results. Finally, section 5 concludes
the paper with future directions of work.

2

RELATED WORK

Multi-attributed graph is used to model many complex problems,
mainly those in which objects or entities are characterized using a
set of features and linked together in different ways. For example,
an online social network user can be characterized using a set of
features like ID, display name, demographic information, interests,
etc. Similarly, two person in an online social network may be associated through different relationships like friendship, kinship,
common interests, common friends, etc [4]. In [15], the authors
proposed a new principled framework for estimating graphs from
multi-attribute data. Their method estimates the partial canonical
correlations that naturally accommodate complex vertex features
instead of estimating the partial correlations. However, when the
vertices of a multi-attributed graph have different dimensions, it
is unclear how to combine the estimated graphs to obtain a single
Markov graph reflecting the structure of the underlying complex
multi-attributed data. In [14], Katenka and Kolaczyk proposed a
method for estimating association networks from multi-attribute
data using canonical correlation as a dependence measure between
two groups of attributes.
Clustering is an unsupervised learning technique which aims to
partition a data set into smaller groups in which elements of a group
are similar and that elements from different groups are dissimilar.

Abulaish et al.
As a result, clustering has broad applications, including the analysis
of business data, spatial data, biological data, social network data,
and time series data [24], and a large number of researchers have
targeted clustering problem [2, 12, 17]. Since graph is a popular data
structure to model structural as well as contextual relationships of
data objects, recently graph data clustering is considered as one of
the interesting and challenging research problems [16, 22], and it
aims to decompose a large graph into different densely connected
components. Some of the applications of the graph clustering is
community detection in online social networks [5, 7, 8], social bot
detection [10, 11], spammer detection [1, 3, 6, 9], functional relation
identification in large protein-protein interaction networks, and so
on. Generally graph clustering methods are based on the concept of
normalized cut, structural density, or modularity[16, 22]. However,
like [20], graphs can be partitioned on the basis of attribute similarity in such a way that vertices having similar attribute vectors
are grouped together to form a cluster. Mainly graph clustering
and simple data clustering differs in the way associations between
objects are calculated. In graph clustering, the degree of association between a pair of objects is calculated as closeness between
the respective nodes of the graph, generally in terms of number
of direct links or paths between them. Whereas, in simple data
clustering, the degree of association between a pair of objects is
calculated in terms of similarity/distance measure between the vector representations of the objects. Both topological structure and
vertex properties of a graph play an important role in many real
applications. For example, in a social graph, vertex properties can
be used to characterize network users, whereas edges can be used
to model different types of relationships between the users.
It can be seen from the discussions mentioned above that most
of the graph analysis approaches have considered only one aspect
of the graph structure and ignored the other aspects, due to which
the generated clusters either have loose intra-cluster structures
or reflect a random vertex properties distribution within clusters.
However, as stated in [24], “an ideal graph clustering should generate clusters which have a cohesive intra-cluster structure with
homogeneous vertex properties, by balancing the structural and
attribute similarities". Therefore, considering both vertex attributes
and links for calculating similarity/distance between the pairs of
vertices in a graph is one of basic requirements for clustering complex multi-attributed graphs. In this paper, we have proposed a
weighted distance function that can transform a multi-attributed
graph into a simple similarity graph on which existing graph clustering algorithms can be applied to identify densely connected
components.

3

PRELIMINARIES AND DISTANCE
MEASURES

In this section, we present the mathematical basis and formulation
of the proposed weighted distance measures for multi-attributed
graph. Starting with the basic mathematical concepts in subsection
3.1, the formulation of the proposed distance function along with
an example is presented in the subsequent subsections.

A Novel Weighted Distance Measure for Multi-Attributed Graph

3.1

Founding Mathematical Concepts

Since the Linear Algebra concepts inner product and norm generally
form the basis for any distance function, we present a brief overview
of these mathematical concepts in this section.
Inner Product: An inner product is a generalized form of the
vector dot product to multiply vectors together in such a way that
the end result is a scalar quantity. If a® = (a 1 , a 2 , ..., an )T and b® =
(b1 , b2 , ..., bn )T are two vectors in the vector space <n , then the
® and defined using
inner product of a® and b® is denoted by h®
a , bi
equation 1 [18].
n
Õ
® = a® · b® = a 1b1 + a 2b2 + · · · + an bn =
h®
a , bi
a i bi
(1)

Compute ’17, November 16–18, 2017, Bhopal, India
(1) kak
® > 0 with kak
® = 0 iff a® = 0
(positivity)
(2) knak
® = nkak
®
(homogeneity)
(3) ka® + b®k ≤ kak
® + kb®k
(triangle inequality)
Some of the well-known norms defined in [21] are as follows:
(1) L1 -norm (aka Manhattan norm): The L 1 -norm of a vector
a® ∈ <n is simply obtained by adding the absolute values
of its components. Formally, the L1 -norm of the vector a® is
represented as kak
® 1 and it can be defined using equation 5.
n
Õ
kak
®1=
|ai |
(5)
i=1

(2) L2 -norm (aka Euclidean norm): The L 2 -norm of a vector
a® ∈ <n is obtained by taking the positive square root of
the sum of the square of its components. Formally, the
L2 -norm of a vector a® is represented as kak
® 2 and it can be
defined using equation 6.
! 1/2
n
Õ
2
kak
®2=
ai
(6)

i=1

b 1 
 
b 2 


 
T
®
h®
a , bi = a b = a 1 a 2 . . . an  . 
 .. 
 
b 
 n


= a 1b 1 + a 2b 2 + · · · + a n b n

(2)

i=1

(3) Infinity-norm (aka max-norm): The Infinity-norm of a vector a® ∈ <n is obtained as maximum of the absolute values
of the components of the vector. Formally, the infinitynorm of the vector a® is represented as kak
® ∞ and it can be
defined using equation 7.

Alternatively, inner product of a® and b® can be defined as a matrix
product of row vector a®T and column vector b® using equation
2. However, as stated in [18], an inner product must satisfy the
® and c® belong to <n ,
following four basic properties, where a,
® b,
and n is a scalar quantity.
(1) h®
a + b® , c®i = h®
a , c®i + hb® , c®i
®
®
(2) hna® , bi = nh®
a , bi
®
®
(3) h®
a , bi = hb , ai
®
(4) h®
a , ai
® > 0 and h®
a , ai
® = 0 iff a® = 0

n

kak
® ∞ = max |ai |
i=1

(4) Lp -norm: The Lp norm of a vector a® ∈ <n is the positive
p th root of the sum of p th power of the absolute value of
the components of the vector. Formally, the Lp -norm of the
vector a® is represented as kak
® p and it can be defined using
equation 8.
! 1/p
n
Õ
p
kak
®p=
|ai |
(8)

Weighted Inner Product: The weighted inner product is generally
used to emphasize certain features (dimensions) through assigning
weight to each dimension of the vector space <n . If d 1 , d 2 , . . . , dn ∈
< are n positive real numbers between 0 and 1 and D is a corresponding diagonal matrix of order n × n, then the weighted inner
product of vectors a® and b® is defined by equation 3 [18]. It can be easily verified that weighted inner product also satisfies the four basic
properties of the inner product mentioned earlier in this section.
d 1

0

T
®
h®
a , biD = a Db =
di ai bi , where D=  .
 ..
i=1

0

n
Õ

0
d2
..
.
0

...
...
..
.
...

0 
0 
.. 
. 
dn 

i=1

(5) Weighted Euclidean norm: The weighted Euclidean norm of
a vector a® ∈ <n is a special case of the Euclidean norm in
which different dimensions of a® can have different weights.
If AT = a®T is a row matrix of order 1 × n, and D is a
diagonal matrix of order n × n whose i th diagonal element
is the weight of the i th dimension of the vector a,
® then the
weighted Euclidean norm of a® is the positive square root of
the product matrix AT DA. In case D is an identity matrix,
this gives simply the Euclidean norm. Formally, for a given
vector a® ∈ <n and a weight (diagonal) matrix D of order
n × n, the weighted Euclidean norm of a® is represented as
kak
® D and defined using equation 9.

(3)

Norm: In linear algebra and related area of mathematics, the
norm on a vector space <n is a function used to assign a non
negative real number to each vector a® ∈ <n . Every inner product
gives a norm that can be used to calculate the length of a vector.
However, not every norm is derived from an inner product [18].
The norm of a vector a® ∈ <n is denoted by kak
® and can be defined
using equation 4.
p
kak
® = h®
a , ai
®
(4)
T
T
®
As given in [18], if a® = (a 1 , a 2 , ..., an ) and b = (b1 , b2 , ..., bn ) are
two vectors of the vector space <n and n > 0 is a scalar quantity,
then every norm satisfies the following three properties.

(7)

! 1/2
n

 1/2
Õ
T
2
kak
® D = A DA
=
di ai

(9)

i=1

3.2

Multi-Attributed Graph

In this section, we present a formal definition of multi-attributed
graph, in which both vertices and edges can be represented as multidimensional vectors. Mathematically, a multi-attributed graph can

Compute ’17, November 16–18, 2017, Bhopal, India

Abulaish et al.

be defined as a quadruple Gm = (V , E, Lv , Le ), where V , ϕ
represents the set of vertices, E ⊆ V × V represents the set of
edges, Lv : V → <n is a vertex-label function that maps each
vertex to an n-dimensional real vector, and Le : E → <m is an
edge-label function that maps each edge to an m-dimensional real
vector. Accordingly, a vertex v ∈ V in a multi-attributed graph can
be represented as an n-dimensional vector v® = (v 1 , v 2 , . . . , vn )T
and an edge between a vertex-pair (u, v) can be represented as an
m-dimensional vector e®(u, v) = (e 1 (u, v), e 2 (u, v), . . . , em (u, v))T .

3.3

Proposed Weighted Distance Measure

In this section, we present our proposed weighted distance measure
for multi-attributed graph that is based on weighted Euclidean norm.
If u = u® = (u 1 , u 2 , . . . , un )T and v = v® = (v 1 , v 2 , . . . , vn )T are
two vertices of a multi-attributed graph and (u, v) = e®(u, v) =
(e 1 (u, v), e 2 (u, v), . . . , em (u, v))T is a multi-labelled edge between
u and v, then the distance between u and v is denoted by ∆(u, v) and
calculated using equation 10, where λ is a scalar value (equation 11),
and I is an identity matrix of order n × n. The value of λ depends on
the aggregate weight, ω(u, v), of the edges between the vertex-pair
(u, v), which is calculated using equation 12. The value of γ > 0 is
a user-supplied threshold, providing flexibility to tune the value of
λ for calculating distance between a vertex-pair. In equation 12, α i
Í
is a constant such that α i ≥ 0 and ni=1 α i = 1.

⇒ (1 + ω 1 ) ≤ (1 + ω 2 )
⇒ (1 + ω 1 )γ ≤ (1 + ω 2 )γ , where γ ≥ 1
⇒ (1+ω1 )γ ≥ (1+ω1 )γ
1
2
⇒ f (ω 1 ) ≥ f (ω 2 )
Hence, λ is a monotonically decreasing function of ω for γ ≥ 1.
Similarly, it can be shown that λ is a monotonically decreasing
function of γ for ω > 0.
Let λ = f (γ ) be a function of γ
Let γ 1 , γ 2 ≥ 1 such that γ 1 ≤ γ 2
⇒ (1 + ω)γ1 ≤ (1 + ω)γ2 , where ω > 0
1
1
⇒ (1+ω)
γ 1 ≥ (1+ω)γ 2
⇒ f (γ 1 ) ≥ f (γ 2 )
Hence, λ is a monotonically decreasing function of γ for ω > 0. 

ω=1

ω=0.75

ω=0.50

ω=0.25

1.1
1
0.9
0.8
0.7
0.6
λ

0.5
0.4

∆(u, v) = ∆(®
u, v)
® = ku® − v®kλI = (u − v)T .λI .(u − v)


 u 1 − v 1  1/2
...


©
 .  ª®
..
= ­­ u 1 − v 1 . . .
 ..  ®
.


u − v 
...
n¬
«
 n

 1/2
= λ(u 1 − v 1 )2 + λ(u 2 − v 2 )2 + · · · + λ(un − vn )2
! 1/2
n
Õ
√
2
(ui − vi )
= λ×
λ
  .
un − vn  ..

0


0.3

 1/2

0
.. 
. 
λ

0.2
0.1
0
0

(10)

2

3

4

5

6

7

8

9 10 11 12 13 14 15 16 17 18 19 20
γ

Figure 1: Visualization of the monotonically decreasing nature of λ for varying γ and ω values

i=1

1
λ=
(1 + ω(u, v))γ
ω(u, v) = α 1e 1 (u, v) + α 2e 2 (u, v) + · · · + αm em (u, v)
n
Õ
α i ei (u, v)
=

1

(11)

It should be noted that if there is no direct link (edge) between a
vertex pair (u, v), then the value of ω(u, v) in equation 11 becomes
zero, leading the value of λ to 1. In this case, the value of ∆(u, v)
is simply an Euclidean distance between the vertex-pair (u, v), as
proved in theorem 3.2.

(12)

i=1

It may be noted that the λ function defined using equation 11 is
a monotonic decreasing function, as proved in theorem 3.1, so that
the distance between a vertex-pair could decrease with increasing
ties between them, and vice-versa. The novelty of the proposed
distance function lies in providing flexibility (i) to assign different
weights to individual edges using α, and (ii) to control the degree
of monotonicity using γ , as shown in figure 1. It may also be noted
that the value of λ will always be 1, if either if ω(u, v) = 0 or γ = 0.
Theorem 3.1. The λ function defined in equation 11 is a monotonically decreasing function.
Proof. Let λ = f (ω) be a function of ω, where ω is the aggregate
weight of edges between a vertex-pair (u, v).
Let ω 1 , ω2 ≥ 0 such that ω 1 ≤ ω 2

Theorem 3.2. In a multi-attributed graph, if there is no edge
between a vertex-pair then the distance between them is simply an
Euclidean distance.
Proof. Let u = u® = (u 1 , u 2 , . . . , un )T and v = v® = (v 1 , v 2 , . . . , vn )T
be two vertices not connected by any edge. Since there is no edge between the vertex-pair (u, v), the edge vector e®(u, v) = (e 1 (u, v), e 2 (u, v), . . . ,
em (u, v))T = 0®.
⇒ e 1 (u, v) = e 2 (u, v) = · · · = em (u, v) = 0
Hence, ω(u, v) = α 1 .e 1 (u, v) + α 2 .e 2 (u, v) + · · · + αm .em (u, v)
= α 1 .0 + α 2 .0 + · · · + αm .0 = 0.
[using equation 12]
1
1
Hence, λ = (1+ω(u,v))
[using equation 11]
γ = (1+0)γ = 1
√
 1/2
Ín
2
Finally, ∆(u, v) = λ × i=1 (ui − vi )
[using equation 10]
√
 1/2
Ín
Ín
2
2  1/2 , which is an
= 1×
=
i=1 (ui − vi )
i=1 (ui − vi )
Euclidean distance between the vertex-pair (u, v).


A Novel Weighted Distance Measure for Multi-Attributed Graph
Algorithm 1 presents a formal way to calculate the distance
between all pairs of vertices of a given multi-attributed graph
using MAGDist. The proposed MAGDist algorithm reads a multiattributed graph using two separate CSV files – one containing
the list of vertex vectors and the other containing the list of edge
vectors, and produces the distance between each vertex-pairs as a
CSV file, wherein each tuple contains a vertex-pair and distance
value. We have also proposed MAGSim algorithm to generate similarity graph using the distance values calculated by the MAGDist
algorithm. The proposed algorithm reads each vertex-pair and its
distance value < i, j, ∆(i, j) > and calculates similarity between the
vertex-pair (i, j) using equation 13.
sim(i, j) = 1 −

∆(i, j)
max {∆(x, y)}

Algorithm 1: MAGDist(Lv , Le , α, γ )

2
3
4
5

6
7
8
9

10

11
12
13
14
15
16
17

Algorithm 2: MAGSim(D)

1
2
3
4

// generating similarity graph corresponding to a
multi-attributed graph
Input : A CSV file D containing vertex-pairs along with
distance output by the MAGDist.
Output : A CSV file G s containing edge-listed similarity graph.
dmax ← getMaxDistance(D);
for each tuple < i, j, ∆(i, j > in D do
∆(i, j)
sim(i, j) = 1 − d
write tuple < i, j, sim(i, j) > into G s ;
max
end

(13)

x,y ∈V

1

Compute ’17, November 16–18, 2017, Bhopal, India

// computing distance between all pairs of
vertices of a multi-attributed graph
Input : CSV files Lv and Le containing list of vertex vectors,
and edge vectors, respectively. An 1D array α[1..m],
Í
wherein α i ≥ 0 and m
i=1 α i = 1 for calculating the
linear combination of edge weights between a pair of
vertices. A positive integer threshold γ representing
the weightage of edges in distance calculation.
Output : A CSV file D containing distance between each pairs
of vertices.
nv ← vertexCount[Lv ] ;
// number of vertices
n ← vertexDimCount[Lv ] ; // vertex vector dimension
m ← edдeDimCount[Le ] ;
// edge vector dimension
V [nv ][n] ← Lv ;
// reading Lv into array V .
for each vertex-pair (i, j) ∈ Le do
// calculating aggregate weight ω(i, j) of the
edges between vertex-pair (i, j).
ω(i, j) ← 0;
for k ← 1 to m do
ω(i, j) = ω(i, j) + α[k] × ek (i, j) ;
// [eqn. 12]
end
// calculating the value of scalar quantity λ
1
;
// [eqn. 11]
λ = (1+ω(i,
j))γ
// calculating distance ∆(i, j) between the
vertex-pair (i, j).
d ← 0;
for k ← 1 to n do
d = d + (V [i][k] − V [j][k])2 ;
end
√
√
∆(i, j) = λ × d ;
// [eqn. 10]
write tuple < i, j, ∆(i, j) > into D ;
end

Example: Figure 2 presents a simpler case of multi-attributed
graph having four vertices in which each vertex is represented as
a two dimensional feature vector and each edge is represented as

an one dimensional vector. In case, there is no direct edge between
a pair of vertices (e.g., v 1 and v 3 ), the corresponding edge vector
is a zero vector. If we simply calculate the Euclidean distance between the vertex-pairs, then the distance between the vertex-pairs
(v 1 , v 2 ), (v 2 , v 3 ), (v 3 , v 4 ) and (v 4 , v 1 ) is same (10 unit), whereas the
distance calculated by the proposed MAGDist differs, based on
the weight of the edges between them. Similarly, the Euclidean
distance
between the vertex-pairs (v 1 , v 3 ) and (v 2 , v 4 ) are same
√
(10 2), but the distance values calculated using MAGDist are different. The distance values between each vertex-pairs of the multiattributed graph calculated using MAGDist for γ = 1 and γ = 2
are is shown in D 1 and D 2 matrices, respectively of figure 2. It can
be observed that giving more weightage to edges by increasing
the value of γ reduces the distance between the respective vertexpairs. Figure 3 presents a multi-attributed graph in which both
vertex and edge labels are multi-dimensional vectors. For example, the edge vector corresponding to the edge connecting v 2 and
v 3 is e®(2, 3) = (0.36, 0.64)T . If we simply calculate the Euclidean
distance between the vertex-pairs, then the distance between the
vertex-pairs (v 1 , v 2 ), (v 2 , v 3 ), (v 3 , v 4 ) and (v 4 , v 1 ) is same (10 unit),
whereas the distance calculated by the proposed MAGDist differs,
based on the weight of the edges between them. The distance values
between each vertex-pairs of the multi-attributed graph calculated
using MAGDist for γ = 1 and γ = 2 are is shown in D 1 and D 2
matrices, respectively of figure 3. It can be observed from these two
distance matrices too that giving more weightage to edges by increasing the value of γ reduces the distance between the respective
vertex-pairs.

4

EXPERIMENTAL SETUP AND RESULTS

To establish the efficacy of the proposed MAGDist distance measure,
we have considered the well-known Iris data set 1 , which contains
total 150 instances of three different categories of Iris flower; 50
instances of each category. The Iris data set can be represented as
a 150 × 5 data matrix, wherein each row represents an Iris flower,
first four columns represent four different attribute values in centimetre, and the 5th column represents class labels (categories) of
the Iris flower as Setosa, Virginica, or Versicolour. Table 1 shows
a partial snapshot of the Iris data set. We model Iris data set as a
multi-attributed similarity graph in which each vertex v ∈ <4 is a
4-dimensional vector representing a particular instance of the Iris
1 http://archive.ics.uci.edu/ml/datasets/Iris

Compute ’17, November 16–18, 2017, Bhopal, India

0 v04
10 10

v3 v1010
3

v4 1.01.0

1010

0 0 9.81
.14
9.81 1414
.14 8.894
.94
9.81
0
7
.
81
1010
9
.
81
0
7
.
81
1.01.0 0.64
0.64 D1D1
1414
.14.14 7.81
7.81 0 0 7.707
.07
8
.
94
10
7
.
07
0
8.94 10
7.07
0
1010

0.250.25

0 0
v
0 01

Abulaish et al.

0.04
v1 0.04

DD2 2

00
99.62
.62
14
14.14
.14
88.00
.00

99..62
62 14
14..14
14
00
66..10
10
66..10
00
10
77..07
5
.
00
07

00
88..00
7
.
07
7.07
00
55..00
0

v2 v20 0

Figure 2: A multi-attributed graph with vertices as multi-dimensional vectors, and distance matrices D 1 , D 2 calculated using
MAGDist algorithm for γ = 1 and γ = 2, respectively

0 0v4
10 10

v4

1.01.0

9.81 1414
.14 8.816
.16
0 0 9.81
.14
9
.
81
0
8
.
16
14
.14
0
8.16 14.14
D1 9.81
D
DD2 2
1
14
.
14
8
.
16
0
7
.
0.36 0.64
0.64
14.14 8.16
0
7.0707
0.36
8.16 1414
.07 0 0
8.16
.14.14 7.707

1010

1.01.0

0.250.25 0.750.75

0 0
v01
0

v3 v31010

v1

0.04
0.04
0.04
0.04

v2

1010
0
0

00
9
.62
9.62
14
.14
14.14
.67
66.67

62 14
14..14
14 66..67
99..62
67
0
6
.
67
14
.
0
6.67 14.14
14
6
.
67
55..00
6.67
00
00
14..14
14 55..00
00
00
14

v2

Figure 3: A multi-attributed graph with both vertices and edges as multi-dimensional vectors, and distance matrices D 1 , D 2
calculated using MAGDist algorithm for γ = 1 and γ = 2, respectively
Table 1: A partial view of the Iris data set
Sepal length
5.1
4.9
4.7
4.6
5.0
...
6.4
6.9
5.5
6.5
5.7
...
6.3
5.8
7.1
6.3
6.5

Sepal width
3.5
3.0
3.2
3.1
3.6
...
3.2
3.1
2.3
2.8
2.8
...
3.3
2.7
3.0
2.9
3.0

Petal length
1.4
1.4
1.3
1.5
1.4
...
4.5
4.9
4.0
4.6
4.5
...
6.0
5.1
5.9
5.6
5.8

Petal width
0.2
0.2
0.2
0.2
0.2
...
1.5
1.5
1.3
1.5
1.3
...
2.5
1.9
2.1
1.8
2.2

Species
Setosa
Setosa
Setosa
Setosa
Setosa
...
versicolor
versicolor
versicolor
versicolor
versicolor
...
virginica
virginica
virginica
virginica
virginica

flower. The edge (similarity) between a vertex-pair (u, v) is determined using equation 14 on the basis of the Gaussian kernel value
defined in equation 15, where σ = 1 is a constant value [23].
(
κ G (u, v) if κ G (u, v) ≥ 0.55
e(u, v) =
(14)
0
otherwise
κ G (u, v) = e

− ku−v2k
2σ

2

(15)

The resulting multi-attributed Iris similarity graph is shown in
figure 4 (termed hereafter as G 1 for rest of the paper), which contains 150 vertices and 2957 edges. In this graph, the instances of
Setosa, Virginica, or Versicolour are shown using triangles, squares,
and circles, respectively. Although κ G (u, u) = 1.0 for all vertices,
we haven’t shown self-loops in this graph. The proposed MAGDist
algorithm is applied over G 1 to calculate distance between all vertexpairs, and finally MAGSim algorithm is applied to generate Iris similarity graph (termed hereafter as G 2 for rest of the paper), which is
shown in figure 5. In [23], the authors have also used Gaussian kernel followed by the concept of nearest-neighbours to generate Iris
similarity graph (termed hereafter as G 3 for rest of the paper) and
applied Markov Clustering (MCL) to classify the instances of the
Iris data into three different categories. Therefore, in order to verify
the significance of our MAGDist and MAGSim algorithms, we have
also applied the MCL over the Iris similarity graphs G 1 and G 2 , and
present a comparative analysis of all clustering results. Figures 6
and 7 present the clustering results after applying MCL over the Iris
similarity graphs G 1 and G 2 , respectively. Table 2 presents the contingency table for the discovered clusters versus true Iris types from
all three different Iris similarity graphs. It can be observed from
this table that, in case of G 2 , only six instances of iris-versicolor
are wrongly grouped with iris-virginica in C 2 and three instances
of iris-virginica are wrongly grouped with iris-versicolor in C 3 ;
whereas in G 1 forty iris-versicolor instances are wrongly grouped
with iris-virginica in C 2 , and in G 3 , one instance of iris-versicolor
is wrongly grouped with iris-setosa in C 1 and fourteen instances of
iris-virginica are wrongly grouped with iris-versicolor in C 3 .

A Novel Weighted Distance Measure for Multi-Attributed Graph

Figure 4: G 1 : Iris data graph modelled as a multi-attributed
graph in which vertices are 4-dimensional real vectors and
edges are the Gaussian similarity (≥ 0.55) between the respective vertices

Compute ’17, November 16–18, 2017, Bhopal, India

Figure 6: Clustering results after applying MCL over the Iris
data graph G 1

Figure 7: Clustering results after applying MCL over the Iris
data graph G 2

Figure 5: G 2 : Iris data graph modelled as a multi-attributed
graph in which vertices are 4-dimensional real vectors and
edges are MAGSim similarity (≥ 0.80) calculated using equation 13

We have also analyzed the significance of different similarity
graph generation methods in terms of True Positive Rate (TPR) and
False Positive Rates (FPR) that are defined using equations 16 and
17, respectively. In these equations, TP is the True Positives, representing the number of correctly classified positive instances, FP is
the False Positives, representing the number of wrongly classified
negative instances, and P and N represent the total number of positive and negative instances, respectively in the data set. Table 3
presents TPR and FPR values for all three different similarity graphs,
showing best results for G 2 , which has been generated using our
proposed MAGDist and MAGSim algorithms.

Table 2: Contingency table for MCL clusters from similarity
graphs generated by three different methods
Clusters
C 1 (triangle)
C 2 (square)
C 3 (circle)

Set
50
0
0

G1
Vir
0
50
0

Ver
0
40
10

Set
50
0
0

G2
Vir
0
47
3

Ver
0
6
44

Set
50
0
0

G 3 [23]
Vir Ver
0
1
36
0
14
49

TPR =

TP
P

(16)

FPR =

FP
N

(17)

Compute ’17, November 16–18, 2017, Bhopal, India

Abulaish et al.

Table 3: Performance comparison of three different methods on Iris data set
Clusters
C 1 (triangle)
C 2 (square)
C 3 (circle)
Average

4.1

G1
TPR FPR
1.00
0.00
1.00
0.40
0.20
0.00
0.73 0.13

G2
TPR FPR
1.00 0.00
0.94 0.06
0.88 0.03
0.94 0.03

G 3 [23]
TPR FPR
1.00 0.01
0.72 0.00
0.98 0.14
0.90 0.05

Evaluation Results on Twitter Data Set

In order to illustrate the application of the proposed distance measure over a real multi-attributed graph, we have considered a Twitter data set of 300 tweets, comprising equal number of tweets related to three different events – NoteBandi (NTB), RyanInternationalSchool (RIS), and Rohingya (ROH). The tweets are modelled as
a multi-attributed graph, wherein each vertex represents a tweet
as an 110-dimensional binary vector based on the top-110 keyterms identified using tf-idf, and two different edges exist between
a vertex-pair – one representing the degree of Hashtags overlap
and the other representing the tweet-time overlap. The similarity
graph is generated using MAGSim algorithm, and shown in figure 8 wherein the instances of NoteBandi, RyanInternationalSchool,
and Rohingya are represented using squares, triangles, and circles,
respectively. Finally, MCL is applied over the similarity graph to
group the tweets into different clusters shown in figure 9. The evaluation of the obtained clusters is given in table 4. It can be seen
from this table that only five instances of RyanInternationalSchool
are wrongly clustered with Rohingya in C 3 .

Figure 8: Similarity graph generated from Twitter data set
(only edges having similarity value > 0.5 are shown)

5

CONCLUSION AND FUTURE WORKS

In this paper, we have proposed a novel weighted distance measure
based on weighted Euclidean norm that can be used to calculate
the distance between vertex-pairs of a multi-attributed graph containing multi-labelled vertices and multiple edges between a single

Figure 9: Clustering results obtained by applying MCL over
the similarity graph of the Twitter data set
Table 4: Evaluation results of the proposed method on Twitter data set
Clusters
C 1 (triangle)
C 2 (square)
C 3 (circle)

Contingency Table
NTB RIS ROH
0
95
0
100
0
0
0
5
100
Average

Evaluation Results
TPR
FPR
1.00
0.00
1.00
0.00
1.00
0.025
1.00
0.008

vertex-pair. The proposed distance measure considers both vertex
and edge weight-vectors, and it is flexible enough to assign different
weightage to different edges and scale the overall edge-weight while
computing the weighted distance between a vertex-pair. We have
also proposed a MAGDist algorithm that reads the lists of vertex and
edge vectors as two separate CSV files and calculates the distance
between each vertex-pairs using the proposed weighted distance
measure. Finally, we have proposed a multi-attributed similarity
graph generation algorithm, MAGSim, which reads the output produced by the MAGDist algorithm and generates a similarity graph,
which can be used by the existing classification and clustering algorithms for various analysis tasks. Since the proposed MAGDist
algorithm reads multi-attributed graph as CSV files containing
vertex and edge vectors, it can be scaled to handle large complex
graphs (aka big graphs). Applying proposed distance measure and
algorithms on (research articles) citation networks and online social
networks to analyze them at different levels of granularity is one
of the future directions of work.

REFERENCES
[1] Muhammad Abulaish and Sajid Yousuf Bhat. 2015. Classifier Ensembles using
Structural Features for Spammer Detection in Online Social Networks. Foundations of Computing and Decision Sciences 40, 2 (2015), 89–105.

A Novel Weighted Distance Measure for Multi-Attributed Graph
[2] Rakesh Agrawal, Johannes Gehrke, Dimitrios Gunopulos, and Prabhakar Raghavan. 1998. Automatic Subspace Clustering of High Dimensional Data for Data
Mining Applications. In Proceedings of the ACM SIGMOD international conference
on Management of data. Seattle, Washington, USA, 94–105.
[3] Faraz Ahmed and Muhammad Abulaish. 2013. A Generic Statistical Approach
for Spam Detection in Online Social Networks. Computer Communications 36,
10-11 (2013), 1120–1129.
[4] Sajid Yousuf Bhat and Muhammad Abulaish. 2013. Analysis and Mining of
Online Social Networks - Emerging Trends and Challenges. WIREs Data Mining
and Knowledge Discovery 3, 6 (2013), 408–444.
[5] Sajid Yousuf Bhat and Muhammad Abulaish. 2014. HOCTracker: Tracking the
Evolution of Hierarchical and Overlapping Communities in Dynamic Social
Networks. IEEE Transactions on Knowledge and Data Engineering 27, 4 (2014),
1019–1032. DOI:http://dx.doi.org/10.1109/TKDE.2014.2349918
[6] Sajid Yousuf Bhat and Muhammad Abulaish. 2014. Using communities against
deception in online social networks. Computer Fraud & Security 2014, 2 (2014),
8–16.
[7] Sajid Yousuf Bhat and Muhammad Abulaish. 2015. OCMiner: A Density-Based
Overlapping Community Detection Method for Social Networks. Intelligent Data
Analysis 19, 4 (2015), 1–31.
[8] Sajid Yousuf Bhat and Muhammad Abulaish. 2017. A Unified Framework for
Community Structure Analysis in Dynamic Social Networks. In Hybrid Intelligence for Social Networks, Hema Banati, Siddhartha Bhattacharyya, Ashish Mani,
and Mario Koppen (Eds.). Springer, 1–21.
[9] Sajid Y. Bhat, Muhammad Abulaish, and Abdulrahman A. Mirza. 2014. Spammer Classification using Ensemble Methods over Structural Social Network
Features. In Proceedings of the 14th IEEE/WIC/ACM International Conference on
Web Intelligence (WIâĂŹ14). Warsaw, Poland, 11–14.
[10] Mohd Fazil and Muhammad Abulaish. 2017. Identifying Active, Reactive, and
Inactive Targets of Socialbots in Twitter. In Proceedings of the IEEE/WIC/ACM
International Conference on Web Intelligence (WIâĂŹ17), Leipzig, Germany. ACM,
573–580.
[11] Mohd Fazil and Muhammad Abulaish. 2017. Why a Socialbot is Effective in
Twitter? A Statistical Insight. In Proceedings of the 9th International Conference on
Communication Systems and Networks (COMSNETS), Social Networking Workshop,
Bengaluru, India. 562–567.

Compute ’17, November 16–18, 2017, Bhopal, India
[12] David Gibson, Jon Kleinberg, and Prabhakar Raghavan. 1998. Inferring Web
Communities from Link Topology. In Proceedings of the Ninth ACM Conference
on Hypertext and Hypermedia. ACM, New York, USA, 225–234.
[13] M. Girvan and M. E. J. Newman. 2002. Community structure in social and
biological networks. In Proceedings of the National Academy of Sciences. USA,
8271–8276.
[14] Natallia Katenka and Eric D. Kolaczyk. 2011. Multi-Attribute Networks and the
Impact of Partial Information on Inference and Characterization. The Annals of
Applied Statistics 6, 3 (2011), 1068–1094.
[15] Mladen Kolar, Han Liu, and Eric P. Xing. 2014. Graph Estimation From MultiAttribute Data. Journal of Machine Learning Research 15 (2014), 1713–1750.
http://jmlr.org/papers/v15/kolar14a.html
[16] M. E. Newman and M. Girvan. 2004. Finding and evaluating community structure
in networks. Physical Review E69, 026113 (Feb 2004).
[17] Raymond T. Ng and Jiawei Han. 1994. Efficient and Effective Clustering Methods
for Spatial Data Mining. In Proceedings of the 20th International Conference on
Very Large Data Bases. Santiago, Chile, 144–155.
[18] Peter J. Olver. 2008. Numerical Analysis Lecture Note. Retrieved on 18.03.2017
from http://www-users.math.umn.edu/~olver/num_/lnn.pdf.
[19] S. E. Schaeffer. 2007. Graph clustering. Computer Science Review 1, 1 (2007),
27–64. DOI:http://dx.doi.org/10.1016/j.cosrev.2007.05.001
[20] Yuanyuan Tian, Richard A. Hankins, and Jignesh M. Patel. 2008. Efficient Aggregation for Graph Summarization. In Proceedings of the ACM SIGMOD International
Conference on Management of Data. Vancouver, Canada, 567–580.
[21] E.W. Weisstein. 2002. Vector Norm. Wolfram MathWorld. Retrieved on 18.03.2017
from http://mathworld.wolfram.com/VectorNorm.html.
[22] Xiaowei Xu, Nurcan Yuruk, Zhidan Feng, and Thomas A. J. Schweiger. 2007.
SCAN: A Structural Clustering Algorithm for Networks. In Proceedings of the
13th ACM SIGKDD International Conference on Knowledge Discovery and Data
Mining. San Jose, California, USA, 824–833.
[23] Mohammed J. Zaki and Wagner Meira Jr. 2014. Data Mining and Analysis:
Fundamental Concepts and Algorithms. Cambridge University Press, New York,
USA.
[24] Yang Zhou, Hong Cheng, and Jeffrey Xu Yu. 2009. Graph Clustering Based on
Structural/Attribute Similarities. VLDB Endowment 2, 1 (Aug 2009), 718–729.
DOI:http://dx.doi.org/10.14778/1687627.1687709

