Unilateral Jaccard Similarity Coefficient
Julio Santisteban Javier L. Tejada Carcamo
Universidad Católica San Pablo Universidad Católica San Pablo
Campus Campiña Paisajista s/n Quinta Vivanco, Campus Campiña Paisajista s/n Quinta Vivanco,
Barrio de San Lázaro Barrio de San Lázaro
Arequipa, Peru Arequipa, Peru
jsantisteban@ucsp.edu.pe jtejadac@ucsp.edu.pe
ABSTRACT d(i, j) = d(j, i) (2)
Similarity measures are essential to solve many pattern recog-
nition problems such as classification, clustering, and re- d(i, j) + d(j, k) ≥ d(i, k) (3)
trieval problems. Various similarity measures are catego- Here for objects i, j and k, where d() is the distance between
rized in both syntactic and semantic relationships. In this objects i and j. Bridge [1] argues that there exists empiri-
paper we present a novel similarity, Unilateral Jaccard Sim- cal evidence of violations against each of the three axioms.
ilarity Coefficient (uJaccard), which doesn’t only take into Yet, there also exists geometric models of similarity which
consideration the space among two points but also the se- take asymmetry into account [10]. Nosofsky points out that
mantics among them. a number of well-known models for asymmetric proximity
data are closely related to the additive similarity and bias
Categories and Subject Descriptors model [5]. Tversky [13] has proposed a different model in or-
der to overcome the metric assumption of geometric models.
E.1 [Data Structures]: Graphs and networks; G.2.2 [Graph
One of the strengths of contrast models is its capability to
Theory]: Graph algorithms
explain asymmetric similarity judgments. Tversky’s asym-
metry may often be characterized in terms of stimulus bias
General Terms and determined by the relative prominence of the stimuli.
Theory |A ∩ B|
sim(a, b) = ,
|A ∩ B| + α|A − B| + β|B − A| (4)
Keywords α, β ≥ 0
Jaccard, distance, similarity
Here A and B represent feature sets for the objects a and b
respectively; the term in the numerator is a function of the
1. INTRODUCTION set of shared features, a measure of similarity, and the last
Since Euclid to today many similarity measures have been two terms in the denominator measure dissimilarity: α and
developed to consider many scenarios in different areas, par- β are real-number weights; when α != β. Jimenez et al. [6],
ticularly in the last century. Similarity measures are used Weeds and Weir [14] and Lee [7] also propose an asymmet-
to compare different kind of data which is fundamentally ric similarity measure based on Tversky’s work. However
important for pattern classification, clustering, and infor- all proposals include a stimulus bias, asymmetric similar-
mation retrieval problems [3]. Similarity relations have gen- ity judgments, which Tversky refers to as human judgment.
erally been dominated by geometric models in which objects Today, similarity measure is deeply embedded into many of
are represented by points in a Euclidean space [12]. Simi- the algorithms used for graph classification, clustering and
larity is defined as “Having the same or nearly the same other tasks. Those techniques are leaving aside the seman-
characteristics” [4], while the metric distance is defined as tic of each vertex and it’s relation among other vertices and
“The property created by the space between two objects or edges.
points”. All metric distance functions must satisfy three ba- In a direct graph, the similarity from U to Z is not the same
sic axioms: minimality and equal self-similarity, symmetry, as the distance from Z to U, this due to the intrinsic features
and triangle inequality. of a direct graph. The similarities are different because the
d(i, i) = d(j, j) ≤ d(i, j) (1) channels are dissimilar. According to Shannon’s informa-
tion 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 flow among the ver-
tex’s channels, we need to be consider it in the similarity. A
similarity does not fit all tasks or cases.
In Natural Langue Processing, where the similarity between
Copyright c 2015 for the individual papers by the papers’ authors. Copy- two words is not symmetric sim(word a,word b) != sim(word
ing permitted for private and academic purposes. This volume is published b,word a). WordNet [4] presents 28 different types of rela-
and copyrighted by its editors.
SIGIR Workshop on Graph Search and Beyond ’15 Santiago, Chile tions; those relations have direction but are not symmetrical,
Published on CEUR-WS: http://ceur-ws.org/Vol-1393/. they are not even synonyms because each synonym word has
same problem. On the other hand we propose a measure
1 2 3
that does not include this bias. We propose a modified ver-
sion of Jaccard Similarity coefficient (1), unilateral Jaccard
Similarity coefficient (uJaccard) (2)(3), used to identify the
y
similarity coefficient of Va to Vc With respect to vertex Va,
x
and to also identify the similarity coefficient of Vc to Va
With respect to vertex Vc.
Figure 1: Structural Equivalence. |a ∩ c|
Jaccard(Va , Vc ) = (5)
|a ∪ c|
a particular semantic, meaning and usage, but are similar. |a ∩ c|
Hence if two words have symmetric distance or similarity, uJaccard(Va , Vc ) = (6)
|edges(a)|
those two words are the same. Paradigmatic is an intrinsic
feature in language, It lets the utterer exchange words with |c ∩ a|
other words, words with similar semantics [11]. In this paper uJaccard(Vc , Va ) = (7)
|edges(c)|
we focus on paradigmatic analysis to support our unilateral
Jaccard Similarity coefficient (uJaccard). Here Va and Vc are the number of edges in vertex a and
The rest of the paper is organized as follows. In section 2 we c, likewise the edges(Vc) are the number of edges in ver-
will show the unilateral Jaccard Similarity coefficient (uJac- tex c. if uJaccard is close to 0, it means that they are not
card). In section 3 we will consider some cases; finally in similar at all. The objective of using uJaccard is to iden-
section 4 we conclude this work. tify how similar a vertex is to other vertices in relation to
itself. uJaccard could be calculated among two connected
2. PARADIGMATIC SIMILARITY DEFINI- vertices, uJaccard could also be calculated among vertices
that are not connected directly, but which are connected
TION by in-between vertices. The number of in-between vertices
could be from 1 to n, we do not recommend a deep compar-
2.1 Basics Of Paradigmatic Structures ison since the semantics of the vertex loosest its meaning.
Paradigmatic analysis is a process that identifies entities Hence max(n)=3, it is suggested for NLP. For the calcula-
which are not related directly but are related by their prop- tions we do not consider the number of in-between vertices
erties, relatedness among other entities and interchangeabil- since we focus on the information flow and not the informa-
ity [2]. In language the reason why we tend to use mor- tion transformation carried out on the intermediate vertices.
phologically unrelated forms in comparative oppositions is
to emphasize the semantics, this is done by substitution and 3. EXPERIMENTAL EVALUATION
transposition of words with a similar signifier. Similarity is
not defined by a syntactic set of rules but rather by the use
of the language. In some cases this use is not grammatically 2 8
or syntactically correct but it is commonly used. We defined 9
the signifier as being the degree of relation among entities
3 7 12
of the same group, where not all members of the group have 1 4 10
the same degree of relatedness. This is due to the fact that
a member of a group might belong to more than one group. 5 11
2.2 Extended Paradigmatic 6
Two vertices in a graph are structurally equivalent if they
share many of the same network neighbours. Figure 1 de- Figure 2: Toy graph.
picts 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 3.1 Toy Testing
share the same neighbours, but they do have neighbours Using similarity uJaccard (6),(7) we can build a paradig-
who are themselves similar [8] [15]. We will use structural matic approach to group vertices. Figure 2 shows a toy
equivalence as the bases of uJaccard. graph with 12 vertices and 16 edges, following the paradig-
matic analysis, we can determine that vertex 12 and 7 belong
2.2.1 Unilateral Jaccard Similarity to group P because they have the same number of edges to
To calculate a paradigmatic similarity we start with a a same set of vertices. Vertex 1 also belongs to group P
question, is the similarity coefficient from vertex Va to Vc because vertex 1 has 3 of the 5 edges, the same as vertex 7,
the same to the similarity coefficient from vertex Vc to Va the degree of membership of vertex 1 is lower than vertices 7
?. If we argue that both similarity coefficients are the same, and 12 because vertex 1 has other edges that are not shared
we are arguing that the edges from the vertices Va and Vc by vertices 7 or 12. In the same manner we can determine
are the same, and it is clear that that is not usually the case. that vertex 8, 9, 10 and 11 belong to group Q because they
Thus both vertices have different sets of edges. One problem have an equal number of edges to the same set of vertices.
with Tversky [13] similarity is the estimation for α and β Similarly vertices 2, 3 and 4 belong to group R, and vertices
which are stimulus bias, generally a human factor. Similarly, 5 and 6 belong to group O. In this example we can eas-
other similarities which are based on Tversky idea, have the ily identify the paradigmatic approach, where two or more
vertices belong to the same group if they have the same or It is shown in figure 3.2 that node 1 might belong to clus-
similar neighbours, but the neighbours in turn belong to an- ter {2,3,4} or cluster {5,6}; to resolve this problem we use
other group. uJaccard similarity measure to find the similarity of node 1
Following the uJaccard similarity and the paradigmatic 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
Table 1: uJaccard calculation from figure 3 that similarities from node 1 to other nodes 2 levels deep,
uJaccard (V1,V7) = 3/5 = 0.600 in which uJaccard(1,3) has a strong similarity over the rest.
uJaccard (V7,V1) = 3/7 = 0.428 We could conclude that node 1 belong to cluster {2,3,4}.
uJaccard (V7,V12) = 4/7 = 0.571 In figure 3.2 also node 1 might belong to cluster {2,3,4} or
uJaccard (V12,V7) = 4/4 = 1.000
Jaccard (V1,V7) = 3/9 = 0.333 4 5
Jaccard (V7,V1) = 3/9 = 0.333
Jaccard (V7,V12) = 4/7 = 0.571 3 1
Jaccard (V12,V7) = 4/7 = 0.571
2 6
approach, the results of the graph in figure 3 are shown in
table 3.1. we notice that uJaccard similarity provides bet- Figure 3: Toy graph.
ter 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 compar-
Table 3: Cut a graph 3.2 using uJaccard
ison between Jaccard and uJaccard. As show in table 3.1
1 level deep 2 levels deep
uJaccard provides a unilateral similarity improving the sym-
uJaccard(1,4) 1/4 uJaccard(1,2) 1/4
metric similarity Jaccard.
uJaccard(1,2) 1/4 uJaccard(1,3) 2/4
Table 3.1 shows three toy graphs, in which we present a
uJaccard(1,5) 1/4 uJaccard(1,4) 1/4
uJaccard(1,6) 1/4 uJaccard(1,5) 1/4
Table 2: Test uJaccard in toy graphs - - uJaccard(1,6) 1/4
uJaccard
sim(2,5)=4/4 cluster {5,6,7} or cluster {8,9,10,11}; this is where uJaccard
2
sim(5,2)=4/6 comes in, being able to solve this problem. Table 4 shows
result of similarities from node 1 to all other nodes on the
1 3 4 Jaccard network in different levels deep. cluster {8,9,10,11} presents
7
sim(2,5)=4/6 the highest number of strong similarities, therefor we can
5 sim(5,2)=4/6 conclude that node 1 belongs to cluster {8,9,10,11}.
6
uJaccard 4 2
sim(7,5)=1/3
6 7 sim(5,7)=1/1 3
5 10 8 Jaccard
sim(7,5)=1/3 1
9 sim(5,7)=1/3
5 8
uJaccard 6 7 11 10
sim(2,4)=3/4
5
8 11 sim(4,2)=3/5 9
12
6 13
2 1 10 Jaccard Figure 4: Toy graph.
14 sim(2,4)=3/6
3
4
7
sim(4,2)=3/6
9 3.3 Social Network
We tested uJaccard against two social network graphs; the
comparison among Jaccard and uJaccard. As show in table first is the coauthorship network of scientists [9] the second
3.1 uJaccard provide an unilateral similarity improving the is the network of Hollywood’s actors1 .
symmetric similarity Jaccard. The first network is the coauthorship network of scientists
working on network theory and experiments, compiled by
3.2 Cut a graph M. Newman [9]. We want to find the top scientists that
In graph theory, a cut is a partition of the vertices of a Newman is similar to or that have paradigmatic similarity.
graph into two disjoint subsets. There are many techniques As shown in table 5 the 3 most of Newman’s paradigmatic
and algorithms to cut a graph, but in some cases there are similar scientists are Callaway, Strogatz and Holme. On the
graphs that are difficult to cut, due to their symmetric dis- 1
The Internet Movie Database: ftp://ftp.fu-
tribution of vertices. berlin.de/pub/misc/movies/database/
Table 4: Cut a graph 3.2 using uJaccard Table 5: uJaccard calculation from 3.3, in search
2 levels deep 3 levels deep paradigmatic scientists to Newman
uJaccard(1,4) 1/3 uJaccard(1,4) 1/3 2 levels deep 3 levels deep 4 levels deep
uJaccard(1,2) 1/3 uJaccard(1,2) 1/3 Scientist Newman is similar to:
uJaccard(1,6) 1/3 uJaccard(1,6) 1/3 Callaway 0.15 Strogatz 1.63 Strogatz 8.25
uJaccard(1,7) 1/3 uJaccard(1,7) 2/3 Strogatz 0.15 Holme 1.59 Callaway 7.85
uJaccard(1,9) 1/3 uJaccard(1,9) 2/3 Watts 0.15 Kleinberg 1.59 Watts 7.81
uJaccard(1,11) 1/3 uJaccard(1,11) 2/3 Hopcroft 0.11 Sole 1.59 Kleinberg 7.18
uJaccard(1,10) 1/3 uJaccard(1,10) 1/3 Scientists that are similar to Newman:
Adler 0.33 Aberg 0.50 Aberg 2.50
Aharony 0.33 Adler 0.66 Adler 14.0
BAIESI, M
PACZUSKI, M
CORRAL, A
Aleksiejuk 0.50 Aharony 0.66 Aharony 14.0
JEDYNAK, M
DEFRAYSSEIX, H
BASSLER, K
SIENKIEWICZ, J
DIAMBRA, L
FRONCZAK, A
KOZMA, B HENGARTNER, N HARI, R
FRONCZAK, P KNUUTILA, J
HOLYST, J KORNISS, G
KUNTZ, P
DAFONTOURACOSTA, L SALAZARCIUDAD, I ILMONIEMI, R
THERAULAZ, G
ROTHMAN, D SANWALANI, V LOUNASMAA, O
LAHTINEN, J GAUTRAIS, J GARCIAFERNANDEZ, J
BUHL, J MENDES, J
ALEKSIEJUK, A GOLTSEV, A
Ancelmeyers 0.66 Alava 0.50 Alava 1.00
AHARONY, A KALAPALA, V TOROCZKAI, Z FERRERICANCHO, R DIGARBO, A
ONNELA, J ADLER, J PORTER, M BAK, P HAMALAINEN, M
VALVERDE, S
ZALIZNYAK, A DENEUBOURG, J
GIRVAN, M SAMUKHIN, A
CLAUSET, A SIMONSEN, I MONTOYA,KOHLER,
J R
KASKI, K ARAUJO, A
MARTIN, M MEUCCI, R SALMELIN, R
MUHAMAD, R ERIKSEN, K ALLARIA, E
CHAKRABORTI, A WARMBRAND, C MUCHA, P TIMMERMANN, L
KERTESZ, J DODDS, P
BERNARDES, A CANCHO, R SOLE, R
STAUFFER, D JIN, E JANSSEN, C
PARK, J DOROGOVTSEV, S KUJALA, J
JARISARAMAKI, J MASLOV, S
KANTO, A MOORE,ANCELMEYERS,
C L
COSTA, U SABEL, C
FRAUENFELDER, H GROSS, J
GASTNER, M SCHRAG, S KEPLER, T ARECCHI, F
SNEPPEN, K DANON,
VEGAREDONDO, F L
SCHNITZLER, A
ALAVA, M WATTS, D RUBI, M FREUND, H
MEYERORTMANNS, H NEWMAN, M VAZQUEZPRADA, M
SZABO, G GLEISER, P RAMASCO, J
LUSSEAU, D MENDOZA, C PARK, E ZAKS, M
BALTHROP, J SMITH, E
ROSVALL, M VRAGOVIC, I
Araujo 0.33 Albert 0.10 Albert 0.50
ARENAS, A FLORIA, L VANNUCCHI, F
GIRALT, F BRAGARD, J TASS, P
CABRALES, A WEULE, M
GOMEZGARDENES, J VOLKMANN, J
FORREST, S GHOSHAL, G SOFFER, S MANCINI, H
LILLO, F DIAZGUILERA, A PACHECO, A
SPATA, A BENNAIM, E GOMEZ, J
CALLAWAY, D ANDRADE, J HENTSCHEL, H MAZA, D
GUIMERA, R LOPEZRUIZ, R CHAVEZ, M ROSENBLUM, M RUDZICK, O
STROGATZ, S LOUIS, E
LEICHT, E MINNHAGEN, P KURTHS, J PIKOVSKY, A
BONANNO, G TURTSCHI, A PASTORSATORRAS, R ECHENIQUE, P
YEUNG, M TRUSINA, A BOGUNA, M OSIPOV, G
MORENO, Y BOCCALETTI, S
BUCOLO, M FORTUNA, L MOREIRA, A PEREZ, C
FORTUNATO, S
USAI, L HOPCROFT, J CHUNG, J HWANG, D VALLADARES, D
CAMACHO, J GUARDIOLA, X
VALLONE, A ABEL, H
FRASCA, M NEKOVEE, M
MIROLLO, R AMANN, A CHATE, H
LAROSA, M MANTEGNA, R VAZQUEZ, A
LLAS, M SCHAFER, C
ERGUN, G LEYVRAZ, F AMARAL, L
COSENZA, S MATTHEWS, P CHOI, M EDLING, C MOSSA, S WEIGT, M ZHOU, C
HOLME, P ANTAL, T GREGOIRE, G
STAGNI, C BARRAT, A LEONE, M PELAEZ, A
PLUCHINO, A
ABERG, Y BARTHELEMY, M
RAPISARDA, A DARBYDOWMAN, K VESPIGNANI, A RADICCHI, F
REMONDINI, D LILJEROS, F SCALA, A
MARCHIORI, M
KLEINBERG, J VAZQUEZ, F KIM, B PARK, H ZECCHINA, R
KRAPIVSKY, P CASTELLANO, C CECCONI, F
CRUCITTI, P RODGERS, G MOTTER, A
STANLEY, H GONDRAN, B
TIERI, P TADIC, B PROVERO, P
FRANCESCHI, C REDNER, S VILONE, D
FLAMMINI, A PECORA, L
LATORA, V HAN, S HONG, H NISHIKAWA, T
UPFAL, E PARISI, D
THURNER, S GUICHARD, E
TOMKINS, A CARUSO, F KIM, J KIM, S LORETO, V
VALENSIN, CASTELLANI,
S YOON, C DEMOURA, A
G HERRMANN, C BARAHONA, M
HUSS, M
RAGHAVAN, P GREBOGI, C
BRODER, A CARROLL, T
MARITAN, A
KUMAR, S KINNEY, R KAHNG, B HEAGY, J
SIVAKUMAR, D OH, E
RAJAGOPALAN, S PORTA, S HOPPENSTEADT, FLAI,
MITRA, M Y
GHIM, C HONG, D DASGUPTA, P
KUMAR, R JUNG, S CIEPLAK, M
GOH, K FINK, K
WIENER, J RHO, K JOHNSON, G
CALDARELLI, G RIGON, R
RODRIGUEZITURBE, I
MAGHOUL, F COLAIORI, F
KIM, D LEE, D HOLTER, N
STATA, R ALBERT, I ALBERT, R BANAVAR, J
JEONG, H
PARK, Y YE, N
COCCETTI, F LIU, Z
CASTRI, M RINALDO, A FEDROFF, N
LAWRENCE, S SERVEDIO, V GIACOMETTI, A
TOMBOR, B ALMAAS, E HERRMANN, H
CAPOCCI, A DELOSRIOS, P
NAKARADO, G MASON, S FARKAS, I BIANCONI,STROUD,
G D
GILES, C SZATHMARY, E PETERMANNN,
GARLASCHELLI, D T
TU, Y
NEDA, Z KOVACS, B BATTISTON, S
PODANI, J SCHUBERT, A
FLAKE, G DEARCANGELIS, L
COETZEE, F YOOK, S MUNOZ, M
DERENYI, I
OLTVAI, ZRAVASZ, E KULKARNI, R ROUX, S GONZALES, M
DOVIDIO, F MACDONALD, P DONETTI, L
GLOVER, E
LOFFREDO, M
PENNOCK, D
VICSEK, T
PIETRONERO, L
The results of the search on the network of top 250 actors
BARABASI, A
SOMERA, A CATANZARO, M
TORRES, J
MARODI, M GORMAN, S
WUCHTY, S
SOUSA, A GARRIDO, P
BEG, Q MONGRU, D
CZIROK, A DOBRIN, R
SHOCHET, O SCHWARTZ, N DELUCIA, M
MARRO, J
WILLIAMS, R
MARTINEZ, N BOTTACCIO, M
BENAVRAHAM, D
COHEN, I DEZSO, Z YUSONG, T
LINGJIANG, K
COHEN, R MONTUORI, M
BERLOW, E
BENJACOB, E DUNNE, J
MUREN, L DICKMAN, R
HAVLIN, S EREZ, K
SHEFI, O
and top 1000 actors, using uJaccard and the paradigmatic
DEMENEZES, M
ROZENFELD, A
SEGEV, R
AYALI, A
GOLDING, I MAKSE, H
PENNA, T SONG, C
MOUKARZEL, C
approach are presented in tables 6 and 7. In table 6 we focus
Figure 5: Coauthorship network of scientists, se- in Tom Cruise, we found that Tom Cruise is most similar
lected nodes belong to scientists Newman, Callaway, to Julia Roberts but Julia Roberts is most similar to John
Strogatz, Holme. 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
other hand the top 3 scientists that are similar to Newman most similar toward Tom Cruise, the most similar towards
are Adler, Aberg and Aharony. uJaccard has been calcu- Tom Cruise is Heath Ledger. Hence this confirm that uJac-
lated in 2,3 and 4 levels deep away from Newman. Newman card helps to identify similarities, particularly asymmetric
is more similar to Strogatz but the most similar scientist to similarities. Table 6 also shows similar scenario among Tom
new Newman is Adler and not Strogatz, even that Strogatz Cruise, Tom Hanks and Joan Allen in the network of top
most similarity is toward Newman. 250 actors and actresses, this confirm the usability of uJac-
For the second network, we created the second social net- card.
work of Hollywood’s actors, we based on The Internet Movie In Table 7 we use the network of top 250 actors and ac-
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 Table 6: uJaccard similarity among top 1000 and
and actresses. The network is composed of nodes represent- top 250 actor and actresses, searching paradigmatic
ing actors and actresses, and vertices are the movies in which similar actor
those actors worked together. A node is created for every Top 1000 actors, cruise tom is similar to:
person, with their names as the key, when two people are roberts julia
in the same movie; a vertex is created between their nodes. roberts julia 0.405 travolta john 0.418
The first network presents 1000 top actors and actresses who hanks tom 0.401 hanks tom 0.412
also work in 41,719 movies with a total 113,478 edges. The jackson samuel 0.399 jackson samuel 0.407
second network presents 250 actors and actresses who work douglas michael 0.397 cruise tom 0.399
in 15,831 movies with a total of 14,096 edges. For this test eastwood clint 0.393 spacey kevin 0.399
we remove duplicated edges. Top 250 actors, cruise tom is similar to:
hanks tom
hanks tom 0.430 douglas michael 0.425
• From a given actor A
douglas michael 0.420 cruise tom 0.421
• We search for actors that actor A is similar to eastwood clint 0.420 jackson samuel 0.418
spacey kevin 0.413 travolta john 0.414
• From the actor A’s similar actor list we get the most jackson samuel 0.410 spacey kevin 0.411
similar actor B Who is similar to cruise tom:
• We search for actors that actor B is similar to top 1000 actors top 250 actors
ledger heath 0.490 allen joan 0.496
• This is done to analyse if actor A and actor B are bacon kevin 0.488 balk fairuza 0.495
reciprocally similar crowe russell 0.482 bello maria 0.488
gibson mel 0.482 collins pauline 0.487
• Then we look for actors that are most similar to actor benigni roberto 0.482 aiello danny 0.487
A
• We do this on the network top 250 actors and top 1000 tresses and we focus on Anthony Quinn and Jack Nicholson.
actors. We start by searching for actors that Anthony Quinn is sim-
ilar to, then we search for actors that are most similar to An- 5. ACKNOWLEDGMENTS
thony Quinn in 1 and 2 levels deep. We notice that Anthony This research was funded in part by ”Fondo para la Inno-
Quinn is most similar to Tom Hanks but most similar ac- vación, Ciencia y Tecnologı́a - Peru” (FINCyT). We thank
tor to Anthony Quinn is Antonio Banderas, while Anthony the Universidad Católica San Pablo for supporting this re-
Quinn is the 153th most similar for Tom Hanks. Antonio search.
Banderas is most similar to Samuel Jackson and not to An-
thony Quinn, while Anthony Quinn is the 53th most similar
for Antonio Banderas. Therefore we could conclude that
6. REFERENCES
Anthony Quinn and Tom Hanks are not symmetric simi- [1] D. Bridge. Defining and combining symmetric and
lar rather they are asymmetric similar. Table 7 also shows asymmetric similarity measures. In B. Smyth and
similar scenario for Jack Nicholson. P. Cunningham, editors, Advances in Case-Based
Reasoning (Procs. of the 4th European Workshop on
Case-Based Reasoning), LNAI 1488, pages 52–63.
Table 7: uJaccard similarity among top 250 actor Springer, 1998.
and actresses, searching paradigmatic actor, in 2 and [2] F. De Saussure and W. Baskin. Course in general
3 levels deep linguistics. Columbia University Press, 2011.
Top 250 actors, are similar to: [3] R. Duda, P. Hart, and D. Stork. Pattern classification
quinn anthony nicholson jack 2nd ed., 2001.
hanks tom 0.451 hanks tom 0.436 [4] C. Fellbaum. Wordnet and wordnets. In A. Barber,
jackson samuel 0.443 eastwood clint 0.429 editor, Encyclopedia of Language and Linguistics,
lemmon jack 0.443 travolta john 0.417 pages 2–665. Elsevier, 2005.
cruise tom 0.435 williams robin 0.417 [5] E. W. Holman. Monotonic models for asymmetric
de niro robert 0.435 douglas michael 0.414 proximities. Journal of Mathematical Psychology,
Who are similar to quinn anthony: 20(1):1–15, 1979.
1 level deep 2 levels deep [6] S. Jimenez, C. Becerra, and A. Gelbukh. Soft
banderas antonio 0.366 banderas antonio 21.866 cardinality: A parameterized similarity function for
bardem javier 0.350 benigni roberto 20.758 text comparison. In Proceedings of the First Joint
martin steve 0.333 burns george 20.565 Conference on Lexical and Computational
goodman john 0.320 baldwin alec 20.413 Semantics-Volume 1: Proceedings of the main
allen woody 0.285 mcqueen steve 20.244 conference and the shared task, and Volume 2:
Who are similar to nicholson jack: Proceedings of the Sixth International Workshop on
1 level deep 2 levels deep Semantic Evaluation, pages 449–453. Association for
greene graham 0.484 banderas antonio 41.477 Computational Linguistics, 2012.
bronson charles 0.482 bacon kevin 41.133 [7] L. Lee, F. C. Pereira, C. Cardie, and R. Mooney.
brody adrien 0.480 baldwin alec 41.0862 Similarity-based models of word cooccurrence
bale christian 0.476 bronson charles 40.982 probabilities. In Machine Learning. Citeseer, 1999.
baldwin alec 0.474 benigni roberto 40.948 [8] F. Lorrain and H. C. White. Structural equivalence of
individuals in social networks. The Journal of
mathematical sociology, 1(1):49–80, 1971.
[9] M. E. Newman. Finding community structure in
4. CONCLUSION networks using the eigenvectors of matrices. Physical
A key assumption of most models of similarity is that a review E, 74(3):036104, 2006.
similarity relation is symmetric. The symmetry assumption [10] R. M. Nosofsky. Stimulus bias, asymmetric similarity,
is not universal, and it is not essential to all applications and classification. Cognitive Psychology, 23(1):94–140,
of similarity. The need for asymmetric similarity is impor- 1991.
tant and central in Information Retrieval and Graph Data [11] M. Sahlgren. The word-space model: Using
Networks. It can improve current methods and provide an distributional analysis to represent syntagmatic and
alternative point of view. paradigmatic relations between words in
We present a novel asymmetric similarity, Unilateral Jaccard high-dimensional vector spaces. 2006.
Similarity (uJaccard), where the similarity among A and B [12] R. N. Shepard. Representation of structure in
is not same to the similarity among B and C, uJaccard(A,B) similarity data: Problems and prospects.
!= uJaccard(B,A); this is based on the idea of paradigmatic Psychometrika, 39(4):373–421, 1974.
association. In comparison to Tversky [13] our approach
[13] A. Tversky. Features of Similarity. In Psychological
uJaccard does not need a stimulus bias, whereas in the case
Review, volume 84, pages 327–352, 1977.
of Tversky human judgement is needed.
[14] J. Weeds and D. Weir. Co-occurrence retrieval: A
We present a series of cases in which we confirmed its use-
flexible framework for lexical distributional similarity.
fulness and we validated uJaccard. We could extend uJac-
Computational Linguistics, 31(4):439–475, 2005.
card to include weights to improve the asymmetry, we could
also use uJaccard and the paradigmatic approach to clus- [15] D. R. White and K. P. Reitz. Graph and semigroup
ter Graph data Networks. These are tasks in which we are homomorphisms on networks of relations. Social
working on. Networks, 5(2):193–234, 1983.
In conclusion, the proposed uJaccard similarity proved to be
useful despite its simplicity and the few resources used.