Similarity measures are essential to solve many pattern recognition problems such as classi cation, clustering, and retrieval problems. Various similarity measures are categorized in both syntactic and semantic relationships. In this paper we present a novel similarity, Unilateral Jaccard Similarity Coe cient (uJaccard), which doesn't only take into consideration the space among two points but also the semantics among them.
Theory
Since Euclid to today many similarity measures have been
developed to consider many scenarios in di erent areas,
particularly in the last century. Similarity measures are used
to compare di erent kind of data which is fundamentally
important for pattern classi cation, clustering, and
information retrieval problems [
d(i; i) = d(j; j) d(i; j) (1) Copyright c 2015 for the individual papers by the papers’ authors. Copying permitted for private and academic purposes. This volume is published and copyrighted by its editors.
SIGIR Workshop on Graph Search and Beyond ’15 Santiago, Chile
Published on CEUR-WS: http://ceur-ws.org/Vol-1393/.
(2)
(3)
(4)
d(i; j) = d(j; i)
d(i; j) + d(j; k)
d(i; k)
Here for objects i, j and k, where d() is the distance between
objects i and j. Bridge [
jA \ Bj
jA \ Bj + jA Bj + jB
;
0
Here A and B represent feature sets for the objects a and b
respectively; the term in the numerator is a function of the
set of shared features, a measure of similarity, and the last
two terms in the denominator measure dissimilarity: and
are real-number weights; when != . Jimenez et al. [
In a direct graph, the similarity from U to Z is not the same as the distance from Z to U, this due to the intrinsic features of a direct graph. The similarities are di erent because the channels are dissimilar. According to Shannon's information theory we could argue that each vertex is a source of energy with an average entropy which is shared among it's channels, and while that information ow among the vertex's channels, we need to be consider it in the similarity. A similarity does not t all tasks or cases.
In Natural Langue Processing, where the similarity between
two words is not symmetric sim(word a,word b) != sim(word
b,word a). WordNet [
The rest of the paper is organized as follows. In section 2 we will show the unilateral Jaccard Similarity coe cient (uJaccard). In section 3 we will consider some cases; nally in section 4 we conclude this work.
PARADIGMATIC SIMILARITY DEFINITION
Basics Of Paradigmatic Structures
Paradigmatic analysis is a process that identi es entities
which are not related directly but are related by their
properties, relatedness among other entities and
interchangeability [
Two vertices in a graph are structurally equivalent if they
share many of the same network neighbours. Figure 1
depicts a structural equivalence between two vertices y and x
who have the same neighbours. Regular equivalence is more
subtle, two regularly equivalent vertices do not necessarily
share the same neighbours, but they do have neighbours
who are themselves similar [
Unilateral Jaccard Similarity
To calculate a paradigmatic similarity we start with a
question, is the similarity coe cient from vertex Va to Vc
the same to the similarity coe cient from vertex Vc to Va
?. If we argue that both similarity coe cients are the same,
we are arguing that the edges from the vertices Va and Vc
are the same, and it is clear that that is not usually the case.
Thus both vertices have di erent sets of edges. One problem
with Tversky [
Jaccard(Va; Vc) = ja \ cj
ja [ cj uJaccard(Va; Vc) = uJaccard(Vc; Va) =
ja \ cj jedges(a)j
jc \ aj jedges(c)j Here Va and Vc are the number of edges in vertex a and c, likewise the edges(Vc) are the number of edges in vertex c. if uJaccard is close to 0, it means that they are not similar at all. The objective of using uJaccard is to identify how similar a vertex is to other vertices in relation to itself. uJaccard could be calculated among two connected vertices, uJaccard could also be calculated among vertices that are not connected directly, but which are connected by in-between vertices. The number of in-between vertices could be from 1 to n, we do not recommend a deep comparison since the semantics of the vertex loosest its meaning. Hence max(n)=3, it is suggested for NLP. For the calculations we do not consider the number of in-between vertices since we focus on the information ow and not the information transformation carried out on the intermediate vertices. 3.
EXPERIMENTAL EVALUATION (5) (6) (7) 1 2 3 4 5 6 7
12 8 9 10 11
Using similarity uJaccard (6),(7) we can build a paradigmatic approach to group vertices. Figure 2 shows a toy graph with 12 vertices and 16 edges, following the paradigmatic analysis, we can determine that vertex 12 and 7 belong to group P because they have the same number of edges to a same set of vertices. Vertex 1 also belongs to group P because vertex 1 has 3 of the 5 edges, the same as vertex 7, the degree of membership of vertex 1 is lower than vertices 7 and 12 because vertex 1 has other edges that are not shared by vertices 7 or 12. In the same manner we can determine that vertex 8, 9, 10 and 11 belong to group Q because they have an equal number of edges to the same set of vertices. Similarly vertices 2, 3 and 4 belong to group R, and vertices 5 and 6 belong to group O. In this example we can easily identify the paradigmatic approach, where two or more 2 7 6 5 1 6 5 3 1 5 10 6 4 7 9 9 8 12 8 13 11 10 14 vertices belong to the same group if they have the same or similar neighbours, but the neighbours in turn belong to another group.
Following the uJaccard similarity and the paradigmatic approach, the results of the graph in gure 3 are shown in table 3.1. we notice that uJaccard similarity provides better information of similarity than Jaccard, this is because uJaccard considers the notion of unilateral similarity. Table 3.1 shows three toy graphs, in which we present a comparison between Jaccard and uJaccard. As show in table 3.1 uJaccard provides a unilateral similarity improving the symmetric similarity Jaccard.
Table 3.1 shows three toy graphs, in which we present a
In graph theory, a cut is a partition of the vertices of a graph into two disjoint subsets. There are many techniques and algorithms to cut a graph, but in some cases there are graphs that are di cult to cut, due to their symmetric distribution of vertices.
It is shown in gure 3.2 that node 1 might belong to cluster f2,3,4g or cluster f5,6g; to resolve this problem we use uJaccard similarity measure to nd the similarity of node 1 to other nodes. Table 3 shows that similarities from node 1 to other nodes 1 level deep are the same, so we could not allocate node 1 to a particular cluster. Table 3 also shows that similarities from node 1 to other nodes 2 levels deep, in which uJaccard(1,3) has a strong similarity over the rest. We could conclude that node 1 belong to cluster f2,3,4g. In gure 3.2 also node 1 might belong to cluster f2,3,4g or 4 2 3
1 cluster f5,6,7g or cluster f8,9,10,11g; this is where uJaccard comes in, being able to solve this problem. Table 4 shows result of similarities from node 1 to all other nodes on the network in di erent levels deep. cluster f8,9,10,11g presents the highest number of strong similarities, therefor we can conclude that node 1 belongs to cluster f8,9,10,11g. 4
2 3 1 5 6 7 8 9 11
10 1The Internet Movie Database: berlin.de/pub/misc/movies/database/ ftp://ftp.fuother hand the top 3 scientists that are similar to Newman are Adler, Ab erg and Aharony. uJaccard has b een calculated in 2,3 and 4 levels deep away from Newman. Newman is more similar to Strogatz but the most similar scientist to new Newman is Adler and not Strogatz, even that Strogatz most similarity is toward Newman.
For the second network, we created the second so cial network of Hollywo o d's actors, we based on The Internet Movie Database (note). We download actors and actresses data, which includes title of movies in which they worked, we also download a list of top 1000 (nota) and top 250 (nota) actors and actresses. The network is comp osed of no des representing actors and actresses, and vertices are the movies in which those actors worked together. A no de is created for every p erson, with their names as the key, when two p eople are in the same movie; a vertex is created b etween their no des. The rst network presents 1000 top actors and actresses who also work in 41,719 movies with a total 113,478 edges. The second network presents 250 actors and actresses who work in 15,831 movies with a total of 14,096 edges. For this test we remove duplicated edges. The results of the search on the network of top 250 actors and top 1000 actors, using uJaccard and the paradigmatic approach are presented in tables 6 and 7. In table 6 we fo cus in Tom Cruise, we found that Tom Cruise is most similar to Julia Roberts but Julia Roberts is most similar to John Travolta, Tom Cruise is third in Julia Roberts ' similarity list. clearly there is not a symmetric similarity among Julia Roberts and Tom Cruise. Moreover Julia Roberts is not the most similar toward Tom Cruise, the most similar towards Tom Cruise is Heath Ledger. Hence this con rm that uJaccard helps to identify similarities, particularly asymmetric similarities. Table 6 also shows similar scenario among Tom Cruise, Tom Hanks and Joan Al len in the network of top 250 actors and actresses, this con rm the usability of uJaccard.
In Table 7 we use the network of top 250 actors and acilar to, then we search for actors that are most similar to Anthony Quinn in 1 and 2 levels deep. We notice that Anthony Quinn is most similar to Tom Hanks but most similar actor to Anthony Quinn is Antonio Banderas, while Anthony Quinn is the 153th most similar for Tom Hanks. Antonio Banderas is most similar to Samuel Jackson and not to Anthony Quinn, while Anthony Quinn is the 53th most similar for Antonio Banderas. Therefore we could conclude that Anthony Quinn and Tom Hanks are not symmetric similar rather they are asymmetric similar. Table 7 also shows similar scenario for Jack Nicholson.
Top 250 actors, are similar to: quinn anthony nicholson jack hanks tom 0.451 hanks tom 0.436 jackson samuel 0.443 eastwood clint 0.429 lemmon jack 0.443 travolta john 0.417 cruise tom 0.435 williams robin 0.417 de niro robert 0.435 douglas michael 0.414
Who are similar to quinn anthony: 1 level deep 2 levels deep banderas antonio 0.366 banderas antonio bardem javier 0.350 benigni roberto martin steve 0.333 burns george goodman john 0.320 baldwin alec allen woody 0.285 mcqueen steve
Who are similar to nicholson jack: 1 level deep 2 levels deep greene graham 0.484 banderas antonio bronson charles 0.482 bacon kevin brody adrien 0.480 baldwin alec bale christian 0.476 bronson charles baldwin alec 0.474 benigni roberto 21.866 20.758 20.565 20.413 20.244 41.477 41.133 41.0862 40.982 40.948
A key assumption of most models of similarity is that a similarity relation is symmetric. The symmetry assumption is not universal, and it is not essential to all applications of similarity. The need for asymmetric similarity is important and central in Information Retrieval and Graph Data Networks. It can improve current methods and provide an alternative point of view.
We present a novel asymmetric similarity, Unilateral Jaccard
Similarity (uJaccard), where the similarity among A and B
is not same to the similarity among B and C, uJaccard(A,B)
!= uJaccard(B,A); this is based on the idea of paradigmatic
association. In comparison to Tversky [
We present a series of cases in which we con rmed its usefulness and we validated uJaccard. We could extend uJaccard to include weights to improve the asymmetry, we could also use uJaccard and the paradigmatic approach to cluster Graph data Networks. These are tasks in which we are working on.
In conclusion, the proposed uJaccard similarity proved to be useful despite its simplicity and the few resources used.
This research was funded in part by "Fondo para la Innovacion, Ciencia y Tecnolog a - Peru" (FINCyT). We thank the Universidad Catolica San Pablo for supporting this research. 6.