%\documentstyle[12pt,/users/faculty/eem/.tex/mymoretext,/users/faculty/eem/.tex/spacing]{article}
%\documentstyle[a4,12pt,times,epsf,/users/faculty/eem/.tex/spacing]{article}
\input epsf 
\documentstyle[twocolumn]{article}
%%% european page dimensions
%\voffset -1cm
%\hoffset -1.0cm                       %moves page right (if positive)
%\textwidth=17.5cm
%\textheight=24.0cm
%\renewcommand{\baselinestretch}{1.0}
%%%% american page dimensions
%-\renewcommand{\baselinestretch}{1.0}
%-\hoffset=-.40in 
%-\voffset=-.50in
%-\textwidth=6.7in
%-\textheight=9.2in

%-\parindent=0.5cm                       %sets paragraph indentation
%-\parskip=0.1cm                         %sets separation between  par.
 
%\raggedbottom
%-\flushbottom
%-\sloppy

%-\setlength{\unitlength}{5.5mm}


%-\pagestyle{plain}

\long\def\invis#1{}

\textheight 8.5in
\textwidth 6.0in
\columnsep 0.37in
\oddsidemargin 0.25in   \evensidemargin 0.25in
\topmargin -.3in   \headheight 0in   \footheight 1in

%%%%% definitions for text formulation %%%%%%
\newcommand{\ifp}{\hspace*{\parindent}}
\newcommand{\ifg}{\hspace*{1.0cm}}
\newcommand{\plotsize}{\epsfxsize 14.0cm}
 
%\newcommand{\ellips}{\cal E}
%\newcommand{\hyperb}{\cal H}
 
\newcommand{\mrk}{\ast\ast\ast}
\newcommand{\beq}{\begin{equation}}
\newcommand{\eeq}{\end{equation}}
\newcommand{\bit}{\begin{itemize}}
\newcommand{\eit}{\end{itemize}}
\newcommand{\tol}{t}
\newcommand{\graph}{graph}
\newcommand{\labelled}{labeled}
\newcommand{\numdims}{f}
\newcommand{\ndims}{k}
%\newcommand{\tol}{\epsilon}            % tolerance
\newcommand{\umax}{u_{max}}
\newcommand{\Dist}{Dist}
\newcommand{\goal}[1]{ GOAL: {{\em #1}} }
\newcommand{\hide}[1]{ }
\newcommand{\comment}[1]{ {\tiny {#1} } } % the regular 
%\newcommand{\comment}[1]{ {\hide{#1} } }
%\newcommand{\attention}[1]{ {\bf {[*** #1 ***]}}}  % the regular/
\newcommand{\attention}[1]{\hide{#1}} 
% \newcommand{\attention}[1]{ \mrk {\bf {#1}} \mrk} 
% \newcommand{\attention}[1]{} %% hide stuff, for final version
% \newcommand{\reminder}[1]{\attention{#1}}
\newcommand{\capt}{\normalsize}
\newtheorem{lemma}{Lemma}
\newtheorem{problem}{Problem}
\newtheorem{dfn}{Definition}
\newcommand{\beqna}{\begin{eqnarray}}
\newcommand{\eeqna}{\end{eqnarray}}
\newcommand{\ben}{\begin{enumerate}}
\newcommand{\een}{\end{enumerate}}

\newcommand{\Zzz}{{\mathbb Z}}
\newcommand{\Rrr}{{\mathbb R}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}

%sets current page number to 1111
%\setcounter{page}{1111}

\title{Node similarity in networked information spaces}

\author{
Wangzhong Lu, Jeannette Janssen, Evangelos Milios, Nathalie Japkowicz  \\
\mbox{}\\
Dalhousie University \\
Halifax, Nova Scotia, Canada, B3H 3J5 
\vspace{2cm}
\mbox{}
}

\date{\today}

\maketitle

\begin{abstract}

Networked information spaces contain information entities,
corresponding to nodes, which are connected by associations,
corresponding to links in the network. Examples of networked
information spaces are: the World Wide Web, where information entities
are web pages, and associations are hyperlinks; the scientific
literature, where information entities are articles and associations
are references to other articles. Similarity between information
entities in a networked information space can be defined not only
based on the content of the information entities, but also based on
the connectivity established by the associations present. This paper
explores the definition of similarity based on connectivity only, and
proposes several algorithms for this purpose.  Our metrics take
advantage of the local neighborhoods of the nodes in the networked
information space. Therefore, explicit availability of the networked
information space is not required, as long as a query engine is
available for following links and extracting the necessary local
neighbourhoods for similarity estimation. Two variations of similarity
estimation between two nodes are described, one based on the separate
local neighbourhoods of the nodes, and another based on the joint
local neighbourhood expanded from both nodes at the same time.  The
algorithms are implemented and evaluated on the citation graph of
computer science. The immediate application of this work is in finding
papers similar to a given paper in a digital library, but they are
also applicable to other networked information spaces, such as the
Web.

\invis{
 The "locale" of the nodes be extracted by querying CiteSeer. Our algorithms
will not require the complete citation graph: it will query CiteSeer to
extract the sub-graph (locale) in the neighborhood of the references of two
papers, and then use these two sub-graphs or one combined graph to compute
similarity of the two papers.
The premise of this research is that similar papers will share similar
references and papers in the reference list are in some sense similar to each
other. The CiteSeer project has proposed a measure of reference similarity
\cite{giles1998} like the TF-IDF measure treating the document as a bag of
references. Our metrics will generalize this measure by taking advantage of
the local neighborhoods of the references in the citation graph. The "locale"
of the references in the citation graph will be extracted by querying
CiteSeer. Our algorithms will not require the complete citation graph: it
will query CiteSeer to extract the sub-graph (locale) in the neighborhood of
the references of two papers, and then use these two sub-graphs or one
combined graph to compute similarity of the two papers.

% possibly assigning more weight to "core" references.

}
 
\end{abstract}

%\newpage

\paragraph{Keywords}
Networked information spaces, document similarity metric, citation graph, 
digital libraries. 
%\newpage


\section{Introduction}
The increasing popularity and prevalence of the Internet has caused
huge amounts of information to become available in networked
form. The model for such information is that of a {\sl networked
information space}, a collection of information entities connected by
links that represent some kind of relationship between the entities. 
The World Wide Web, seen as a collection of web pages connected by
hyperlinks, is a well-known example of a large networked information space.
The body of scientific literature, where information entities are articles and
links represent references to other articles, has existed as a
networked information space in paper form for many years, and is
rapidly becoming available in electronic form through digital libraries
and the World Wide Web.

In order to navigate and mine the contents of a networked information
space, it is of crucial importance to be able to judge similarity
between information entities.  Traditionally, similarity between
information entities is computed based on their content. However, in a
networked information space, a lot of information about similarity is
encoded in the link structure of the graph. This link-based similarity
can complement the traditional content-based similarity to produce a
higly accurate similarity metric.

In this paper, we explore various similarity metrics purely based on
link structure. Our goal here is to show how much similarity
information can be extracted just from the link structure. Therefore,
we have not included any content-based comparison in our methods. Our
methods are easy to compute. Moreover, they are based only on a local
neighbourhood of the information entities in the networked information
space.  Therefore, they are applicable even when the networked
information space is too large to fit on a desktop machine, provided a
mechanism is available for local navigation from one information
entity to its neighbours.

The link structure of a networked information space can be
modelled as a graph. The nodes of the graph correpond to the
information entities, while the (directed or undirected) edges of the
graph represent the links between information entities. Our similarity
metrics are based on graph-theoretic notions and methods. The first is
based on a network flow computation, the second is based on a
comparison of subgraphs based on hub and authority values.

We apply our methods to the networked information
space formed by the body of computer science literature. The graph
representing this information space will be called the {\sl citation
graph}. The nodes of the citation graphs represent Computer Science
papers. The (directed) edges of the graph represent citation
relations: there is an edge from Paper A to Paper B if Paper A
references Paper B. 
The premise of this research is that similar papers will share similar
references and papers in the reference list are in some sense similar to each
other. Therefore, an analysis of the local neighbourhood (in the
graph-theoretic sense) of a paper will likely lead to a good
similarity metric. For access to the computer science literature we
use the electronic database {\sl ResearchIndex} \cite{giles1998}.

If some scientific paper is of interest to a researcher, then any
documents related to this paper are likely to be similarly
useful. Citation indexes and digital libraries are interested in
classifying the concept of similarity and finding efficient methods to
locate similar papers, so that they can better aid the researcher is
his search.  Several metrics have been proposed to classify similarity
among scientific papers. They fall into three categories: text string
distance \cite{leven1965}; distance based on word/document vectors
(for example vectors of Term Frequency x Inverse Document
frequency(TFIDF) \cite{giles1998}); 
and distance based on citation
information about the documents.

Use of citation
information to compute relatedness between scientific papers has
attracted more and more attention lately.  
Citations of other papers are hand-picked by the
authors as being related to their research.  Therefore, the reference
list of a paper contains information which can be exploited to judge
relatedness.  Two different citation relations between papers have
been specifically identified and used to calculate similarity, namely
co-citation (two papers referenced by the same paper) and bibliographic
coupling (two papers citing the same paper) \cite{small1973}. 

C.~Lee Giles et al.~\cite{giles1998} proposed a similarity measure
based on common citations to judge the relatedness between papers.
The metric, called "Common Citation x Inverse Document
Frequency"(CCIDF) \cite{giles1998}, is similar to the text-based
similarity metric "Term Frequency x Inverse Document
Frequency"(TFIDF). The CCIDF metric assigns a weight to each paper,
which is equal to the inverse of citation frequency in the entire
database.  To find documents related to a given paper, all the papers
which have at least one reference in common with that specific paper
are generated. The CCIDF metric is used by the automatic citation
indexing system of {\sl ResearchIndex}.

Citation analysis was first introduced by \cite{garfield} to measure
the importance of scientific papers.  Citation information has also
been studied in Bibliometrics research to estimate importance and
similarity among research papers
\cite{rousseau}.  
Graph theoretic analysis has been used before to solve problems in
bibliometry and World Wide Web. Small has proposed methods to analyze
the structure of scientific literature using citation graph
\cite{small1974} and to study the co-citation pattern
\cite{small1973}.  

Dean and Henzinger \cite{dean1999} have developed
algorithms which aim to identify related web pages using only
the connectivity information in the web.  Their algorithms use
authority weights and co-citation frequency to judge the relatedness
among web pages.

{\tt jj: Here we need to specify in what way our methods are different
from theirs!}

The reason for using the citation graph instead of comparing reference lists
\cite{giles1998} is that the citation graph contains information which
is much richer than that contained in the reference lists, and which
cannot be obtained just by comparing reference lists from different
papers.  Two papers may have no co-citation or bibliographic coupling
relationship at all, but they could still have a strong relationship
between them if their local citation graphs intersect
substantially. For example, in Figure \ref{fig1} paper $A$ references
paper $C$, paper $B$ references paper $D$, but $A$ and $B$ do not
reference each other. Obviously, paper $A$ and paper $B$ are not
related to each other in terms of CCIDF, co-citation or bibliographic
coupling (i.e.~through their direct references). But if we expand the
citation graph a little bit further, we may find out that papers $C$ and
$D$ are strongly connected by bibliographic coupling links, and we
could infer the relationship between papers $A$ and $B$ from papers
$C$ and $D$. Our method generalizes this notion by using both
citations and references in the neighourhood of two papers.

% \begin{singlespace}
 \begin{figure}
 \epsfxsize =2.3in
 \epsfysize =2in
 \centerline {\epsfbox{figNew/graph1.eps}}
 \caption{Relation between papers inferred from citation graph}
 \label{fig1}
 \end{figure}
% \end{singlespace}

We propose two different graph-based metrics: the maximum-flow metric
and the authority vector metric.  In the maximum-flow metric, one
local citation graph is generated from a pair of papers to be
compared.  One paper is treated as a source node and the other as a
sink node.  Flow capacities are assigned to the edges. Then, the value
of the maximum flow which could be pushed through from source node to
sink node is computed, and used to represent the similarity between
the two papers.  In the authority-based metric, a local citation graph
is grown separately for each paper to be compared. Then, authority
weights are computed for all nodes in each of the local citation
graphs. Each paper is then represented by a vector, whose elements are
the authority weights of the nodes in its local citation
graph. Finally, similarity is computed as the vector distance between
these vectors.

We implemented our methods on a subgraph of the full citation graph of
computer science literature, obtained by querying the electronic
database {\sl ResearchIndex}. In Section 2, we discuss the details of
the local and global citation graph. In Section 3, we describe our
metrics and the methods to compute them. In Section 4, we describe the
mechanics of obtaining and maintaining the graphs needed for the
similarity computation. Finally, in Section 5 we discuss the results
of our methods and the effect on the methods of the values of certain
parameters in our methods, and we compare the results of our
similarity search with that of more conventional methods.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Citation Graph}                                
\label{sec:Citationgraph}

A citation graph is a directed graph representing a body of scientific
literature, linked together by referencing. Nodes of the citation
graph correspond to scientific papers, and a directed link from one
node to another indicates that the paper associated with the first
node references the paper associated with the second node. Since the
references in a given paper are necessarily related to the content of
that paper, the link structure of a citation graph contains indirect
information about the content of the papers.  Hence citation graphs
can be employed to analyze and judge the relationship between papers,
and can also be used to characterize the properties of communities of
research papers.

In this study, we consider the body of literature in Computer
Science. We will use the term {\sl global citation graph} to denote
the graph representing all research papers treating topics in computer
science. However, nowhere is this graph available in its
totality. Several research indices contain large amounts of papers and
reference information, but, due to the enormous amounts of
conferences, journals and preprint series, as well as the overlap
between different disciplines, no such index can pretend to be
complete. 

{\sl ResearchIndex} (formerly {\sl CiteSeer}) is a scientific
literature digital library that aims to provide efficient access to
research papers and their citation information.  It contains over
300,000 documents and over 4 millions citations.  It is an autonomous
citation indexing system which automatically locate papers on the
Internet and indexes them in its database. We chose use this dabase
for our study since it is one of the largest, most comprehensive
collections of computer science literature, it contains the most
recent papers, and it is available through the World Wide Web.
{\sl ResearchIndex} only contains papers that are available in
electronic form, and thus by its nature can never contain older
papers. Nonetheless, the citation graph representing all papers in {\sl
ResearchIndex} is a substantial subgraph of the global citation
graph. 

In our research we compute the similarity between two research papers
based on a {\sl local citation graph}.  A local citation graph is a
small subgraph of the global citation graph, representing the graph
neighborhood of one or two root papers. Local citation graphs
can be extracted from {\sl ResearchIndex} by starting from the root
paper(s), and recursively gathering all the references and papers
citing papers already present. Since {\sl ResearchIndex} is accessible
through the Web, a webrobot can be used to build the local citation graph.

In our research we grow the local citation graph from one or two papers for
several levels, depending upon experimental accuracy requirements and
computational and storage overhead.  For instance, a graph of one level only
consists of papers which have a direct citation relation with the root paper.
This graph is not enough if we want to retrieve related papers which are more
than two links away from the root paper. In our experiments, we expand the
local citation graph both backward and forward in time. Growing the graph
backward in time is to add nodes that are cited by the current node and edges
among them, while expanding the graph forward in time means adding nodes
which reference the current node and adding links among them to the graph as
well. In our current experiment we treat all citations equally.

The local citation graphs used here are all subgraphs of the {\sl
ResearchIndex} citation graph. This means that some information from
the global citation graph is missing; for example, if two papers are
both cited by a paper that is not in the {\sl ResearchIndex} database,
then the co-citation relationship between them is not visible in the
local citation graph. This problem is unavoidable and its effect will
depend on the quality of the database. However, since our methods
consider simultaneously various types of citation relationships, we
expect that our methods will do better than most in minimizing the
effect of the limitations of the database.

A citation or reference is made in one paper and points to another
paper. In this sense a citation link has a direction.  In our
research we use the direction of the citation link to build the local
citation graph from one or two root papers.  In our authority vector
metric, we use the direction to compute authority weight for each node
in the local citation graph.  Then we remove the direction when we do
the similarity computation.  One of our metrics computes a maximum
flow value to judge the similarity between two papers. In this case,
we ignore the direction of the edges, because both citations and
references indicate similarity.

\subsection{Bibliographic coupling and co-citation in the citation graph}

As indicated in the introduction, some specific citation relations
have been used before to judge similarity between scientific papers.
Each of them has its own pattern in the citation graph.  

The first case is the bibliographic coupling relation, which is shown in
Figure \ref{refcoupling}. Two papers are bibliographically coupled if they
reference the same paper. If two recent papers are published in the same or
similar research area, a bibliographic coupling pattern is very likely to be
found in their local citation graph (Figure \ref{refcoupling}).

\begin{figure}
\epsfxsize =2.3in
\epsfysize =1.5in
\centerline {\epsfbox{figNew/ref_coupling.eps}}
\caption{Bibliographic coupling relationship between papers}
\label{refcoupling}
\end{figure}

The second case is the co-citation relation, which is shown in Figure
\ref{cocitation}.  Two papers are related by co-citation if they are
cited together by the same paper. Small has studied the co-citation
pattern among research papers and highlights its importance in similarity
computation \cite{small1973}. In the local citation graph of two related
older papers, co-citation links are often present.

\begin{figure}
\epsfxsize =2.3in
\epsfysize =1.5in
\centerline {\epsfbox{figNew/co_citation.eps}}
\caption{Co-citation relationship between papers}
\label{cocitation}
\end{figure}

The third case is a direct link or direct citation between papers. Direct
citation is likely to happen among related papers which are published apart
in time. It does not occur very frequently among papers published in the same
year or very close in time.

Bibliographic coupling and co-citation have been employed to compute
similarity between research papers. But each of them is only suitable
for computing similarity in specific cases.  For instance researchers
have used co-citation frequency to compute relatedness between two
papers, but the papers to be judged have to be well cited by other
authors for the algorithm to work properly.  Apparently co-citation is
not efficient in judging similarity among recent papers which have not
yet had the chance to be cited by many other authors.  In terms of the
direct link pattern, if the two papers are published almost at the
same time, a direct citation link is not likely to be found between
them, even if their content is related.  Similarly, papers which
appeared in the early stages of the development of a research
specialty are not good candidates for bibliographic coupling analysis.
However, by using the local citation graph in our metrics, we do not need
to know which of these citation patterns our papers fall under. All
patterns of citation relations are accounted for by using the citation
graph.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Similarity metrics based on the citation graph} 
\label{sec:similarity_metric}

We designed two graph-based similarity metrics. One metric is based on
how strongly the two papers are connected in the citation graph.
Another metric measures how similar the two local citation communities
are. The first metric is computed using a maximum flow/minimum cut
value, using an efficient graph-theoretic algorithm, to find out the
amount of flow that can be pushed from one paper to the other.
Obviously the more flow can be pushed from source to sink, the more
paths there are between them, which means the stronger they are
connected. In the second metric, we use vectors to compute
similarity. In each local citation graph we assign an authority
weight to every node.  Then we construct two vectors of the nodes in
both local citation graphs, the elements of which are the authority
weights.  The original idea behind this scheme is that two papers are
similar if their individual local citation graphs share similar
authority papers.

%%%%%%%%%%%%%%%%%%%%%% 
\subsection{Authority Vector metrics}
\label{sec:metric1}

Given two research papers A and B, we construct two separate local citation
graphs, graph A and graph B, for each of them. The idea is to compute
similarity by comparing the similarity of the two citation communities.  It
is not a trivial problem to compare graphs. Rather than comparing local
citation graphs directly, we use authority papers to represent a specific
citation community and compute the similarity between these.  In our work
we want to find a good way to define and find authoritative papers in each
local citation graph.

\subsubsection{Authority paper}

One problem needs to be addressed first, namely how to identify
authority, in other words, what is the criterion to judge the
importance of a given paper.  In bibliometrics, citation analysis was
used to measure the importance of scientific papers by Garfield
\cite{garfield}. Garfield also proposed a well-known metric to
estimate the importance of journals by Impact Factor
\cite{garfield72}.  This metric, in graph-theoretic terms, amounts to
a pure counting of the in-degree of nodes in the citation graph to
compute how importance a journal is.  In ranking search results on the
World Wide Web, people face the problem of how to determine the
importance of a web page.  Brin and Page proposed the PageRank
algorithm \cite{brin1998}.  Kleinberg proposed a more stable measure
of the importance of web page by computing hub and authority weights
\cite{kleinberg1997}. A hub is a paper that points to many
authorities; an authority is a page that is pointed to by many
hubs. An iterative algorithm was proposed to compute hub and authority
papers.

In the citation graph, authority papers are expected to be the core or
the most important papers in a specific research area. Hub papers
might be review papers or survey papers; their content is broad and
therefore they may not be a good basis for characterizing the research
direction. Two papers are probably more similar to each other if they
are connected by reference coupling or co-citation by authority papers
than by hub papers.  So we choose authority weights in our similarity
computation. 
In order to get high similarity between two papers, their graphs must
have a large intersection and there must be many authority papers in
the intersection area. 

Finally, note that our metric is different from CCIDF, the
citation-based metric used by {\sl ResearchIndex} to locate related
papers. First of all, CCIDF uses in-degree as a measure of
importance. Our metric uses authority weight, which
is a more subtle measure of importance than in-degree. Also
CCIDF is based on the citation frequency over the entire citation
graph, while to compute our metric only a local citation graph is needed.

\subsubsection{Algorithm} 

Given two papers, taking each of the papers as a seed, we build two separate
local citation graphs, each consisting of $k$ levels. Then we compute hub and
authority weight for nodes for each of the graphs.  We associate with each
of the two papers a vector indexed by the nodes in the union of the two
graphs.  The component corresponding to a node has value $0$ if the node is
not in that graph. Otherwise, the value of the component is the authority
weight of that node. Both vectors are normalized to length 1.  Finally we
obtain the similarity of the two papers by computing the cosine distance of
the two corresponding vectors.
 For detailed information regarding the algorithm, please refer to
\cite{luthesis}.

\subsubsection{Survey paper effect}

This metric also is expected to reduce the negative effect of survey
or thesis papers. These kinds of papers will be more likely to have
long list of references, hence they are linked to many papers and can
thus be wrongly treated as related to many other papers. In our
authority vector metric, normalizing the vector before computing
similarity will greatly lessen the negative influence of those papers.
The local citation graph of survey papers will be larger than that of
other research papers, and thus the vector of authority weights will
have lots of components. If a vector has lots of components and is
normalized, then in general individual entries will have lesser
values, since they need to add up to 1. This will make the inner product
smaller and hence lead to lower similarity with other papers.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Minimum cut/Maximum flow metric}
\label{sec:metric3}

The key idea of this algorithm is to count the number of different
paths in the citation graph between nodes representing two papers. The
number of paths between two nodes is related to the {\sl minimum cut}, the
minimum number of edges needed to be cut to disconnect one node from
the other. Therefore, our metric is based on a maximum flow/minimum
cut computation in a local citation graph build from the two papers
simultaneously. The capacities of the edges are chosen judiciously, to
represent the fact that longer paths are less indicative of similarity
than longer ones.

\subsubsection{From paths to flows}

Finding all the possible paths between two nodes is not a simple task,
so we have developed our idea into an easily computable metric. We
introduce a flow idea to compute the similarity problem.  This can be
seen as follows: all the paths together constitute a flow. Consider
the task of modeling a network with one source and one sink, in which
the amount of flow between source and sink is restricted by the number
and capacity of the links.  The maximum flow from source to sink can
be efficiently computed and is equal to the minimum capacity of a cut
of the graph between source and sink, where a cut is a set of links
and nodes that disconnect the graph (see \cite{diestel}). Intuitively
the more links and the higher the capacity of links between source and
sink, the more flow can be sent through, and the more links will need
to be cut to disconnect the source from the sink.

Based on this idea, we want to use maximum flow/minimum cut to judge the
relation between two papers.  To count longer paths less, we need to adjust
the capacities, which is the maximum value of flow that could be pushed
through each edge. If we assign high capacity to an edge, we allow
more flow to be pushed through it. The detailed definition of capacity is
given in section \ref{weight}. The idea is that we associate the weight of an
edge with its distance to source or sink papers.  It means that an edge which
is far away from the source or sink paper gets a lower capacity weight.
Imagine an edge in the middle of a longer path. It must get lower capacity
weight according to our weight definition.  Therefore, you can not push more
flow through a longer paths, and, as a result, a longer path will contribute
less to the overall flow from source to sink.  We use the maximum
flow/minimum cut to compute the relatedness of two papers.  The more flow
that can be pushed through, the higher the similarity will be. The idea is
shown in figure \ref{flow}.

 \begin{figure}
 \epsfxsize =2.3in
 \epsfysize =2.5in
 \centerline{\epsfbox{figNew/flow2.eps}}
 \caption{Using minimum cut to compute similarity between papers.}
 \label{flow}
 \end{figure}

In this metric, we do not care about the direction of each edge, since we try
to find out how strongly the two papers are connected together in a
undirected graph grown from the papers to be compared. This is done so that
paths of all types are taken into consideration.


\subsubsection{Capicity assignment}
\label{weight}

Also we use the parameter $d$ to represent the
relationship between longer and shorter paths, in that $d$ paths of length
$k$ are equivalent to 1 path of length $k-1$. Parameter $d$ is an important
factor which is employed to produce quantitative estimates of the importance
of path of a variety of length.

This similarity metric uses a parameter $d$, used to control the
weight of paths of different length. It is chosen so that one path of
length $l$ between two nodes will result in a similarity weight of
$(1/d)^l$.  Greater $d$ means that the weight of a path will drop
faster with the increase of its length.  Parameter $d$ should be
chosen to represent the number of paths of length two that are
considered equivalent to a direct edge between two nodes. In other
words, the similarity metric should give the same value for two
adjacent nodes as for two non-adjacent nodes having $d$ common
neighbors. Note that in the first case, the nodes can be separated by
cutting one edge, while in the second case, $d$ edges must be
cut. This suggests that the capacity of the edge in the first scenario
should be $d$ times as high as the capacity of the edges in the second
scenario. In view of the above, a reasonable choice for $d$ should
depend on the maximum or average degree in the graph, or the maximum
or average number of common neighbors of any pair of nodes.

The argument suggests a capacity of the form $c(e)\sim (1/d)^k$, where
$k$ should be related to the distance of the endpoints of $e$ to $\{
u,v\}$. Finally, we note that every induced path of odd length will
have an edge whose endpoints are at equal distance from $\{ u,v\}$,
while there is no such edge in an induced path of even length. This
suggests assigning a capacity to the nodes also; a path of length two
could then be cut by removing the middle node, which would have
lower capacity than the adjoining edges. However, we can obtain an
equivalent formulation using only edge capacities.

Let the capacity of an edge for parameter $d$, $c_d:E(G^k[u,v])\rightarrow
R$, be defined as follows. For each edge $e=ww'$, 
 \[
c_d(e)=\left\{\begin{array}{ll}
\mbox{if $d(w,\{u,v\}) = $}&\mbox{$d(w',\{ u,v\})$}\\
&\left(\frac{1}{d}\right)^{2d( w,\{u,v\})}\\
\mbox{otherwise}&\\
&\left(\frac{1}{d}\right)^{2d(\{w,w'\},\{u,v\})+1}
\end{array}
\right.
 \]
 where $d(w,\{u,v\})$ is the shortest distance from $w$ to $u$ and $v$. We
treat a direct link between source and sink differently, by giving it a
capacity $\frac{1}{d}$.

After experimentation, we noticed that a direct link between the
papers under consideration skewed the computation result. Hence we
decided to set the capacity of an edge which is a direct link between
source and sink papers as equal to that of a node at distance one, in
other words we treat a direct link as equally importance as a path of
length two which could be co-citation or reference coupling.  We tested
several options for the assignment of capacities in our experiments.
The capacities assigned in our research are based on the length of the
path or the distance between edge and source/sink papers.  We mention
here another option of setting edge capacities, which is based on how
much you trust the edge in similarity computation.  

\subsubsection{Algorithm}

Given two papers, we take both of them as a seed, and build a common
local citation graph of $k$ levels. We then make the graph undirected, so
we assume that flow can go in either direction through an edge. We assign
capacities to all edges of the local citation graph according to the
formula given in \ref{weights}. Then, using a standard maximum
flow/minimum cut algorithm, we compute the maximum amount of flow that
can go between the two papers, given the assigned capacities. This
value represents the measure of similarity between both papers.
For detailed information regarding the algorithm, please refer to
\cite{luthesis}.


\section{Building the local citation graph}

In this section we describe in detail how the local citation graphs
are obtained.  The local citation graph will be built from one or two
papers, and it will be given as input to our similarity metric
computation.  In our implementation there is a module called the graph
building module.  It takes one or two papers as starting points, which
are called seed papers. It will then build a local citation graph by
reading information from our experiment database, which is our locally
stored representation of a part of the {\sl ResearchIndex} database.
Given two research papers, we can grow the graph backward in time,
which means we retrieve the papers in reference list.  At the same
time, we also can go forward to retrieve papers citing the given
papers.  In our research we expand the local citation graph in both
directions in order to make the graph consistent.  In other words, we
want to reconstruct the locale around one or two papers in the citation
community.

The module will expand the graph from seed papers by querying citing
papers and cited papers of the seed papers. We obtain a set of papers
which are directly connected to the seed papers.  Then we expand each
node in this set backward and forward once again, building a larger
set of papers.  By doing this several times we can grow the graph to a
certain size which contains enough information to calculate
similarity.  In our experiment we set a threshold of the number of
times that the graph is expanded back and forth to keep the size of
graph under control.  We use the term layer to represent different
sets of nodes.  Nodes in layer $0$ only contain the starting points
corresponding to the seed papers.  Nodes in layer $1$ are nodes citing
or cited by layer $0$ nodes.  Nodes in layer $2$ are nodes citing or
cited by nodes in layer $1$, but not by nodes in layer $0$.  In terms
of edges, we say that edge $e$ is in layer $n$ if one endpoint of $e$
is in layer $n$ and the other endpoint is in layer $n-1$.  If both
endpoints of an edge are in layer $n$, we say that the edge is in
layer $n.5$.  For instance, if an edge has its endpoints in layer $1$
and layer $2$, we call it a layer $2$ edge; if both endpoints of an
edge are in layer $2$, we call it a layer $2.5$ edge.  In terms of the local
citation graph, we use the maximum layer number to name the layer of a
graph.  For example, a $2.5$ layer graph will include nodes in layer
$0$, $1$ and $2$, and edges in layer $0.5$, $1$, $1.5$, $2$ and $2.5$.
The process of building our local citation graph is shown in figure
\ref{graphgrow}.

 \begin{figure}
 \epsfxsize =2.3in
%\epsfysize =2.3in
 \centerline{\epsfbox{figNew/graphgrow2.eps}}
 \caption{This figure shows the process of growing local citation graph.}
 \label{graphgrow}
 \end{figure}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Evaluation}
\label{evaluation}

Our metrics were tested on a total of 15 papers, all from the field of
neural networks. For each of these papers, we used our methods to find
a result set of papers that are most related to it according to each
of our similarity metrics. The relatedness of the result set was
judged by two of the authors, Evangelos E. Milios and Nathalie
Japkowicz, who are domain experts. In general, our methods compared
very favourably to CCIDF, the graph-based method used by {\sl
ResearchIndex}. In this section, we describe the details of our
experiments, and discuss the effect of the setting of parameters and
other implementation decisions on the results.

All test results are shown in precision diagrams, that are obtained
from the response of our domain experts. The domain experts rated each
of the top ten papers in each result set as `related', `somewhat
related' or `not related', expressed by numerical values 1, $0.5$ and
0, respectively. In the precision diagrams, the total score of the
first $x$ papers in a result set is plotted as a function of $x$. In
total, over 500 papers were rated by the domain experts. The precision
diagrams represent the average results over all papers considered.

{\tt Is the above correct?}

\subsection{Comparitive Results}
\label{comparison}

The main goal of our experiments was to compare the performance of the
maximum flow metric and the authority metric and CCIDF.
It is interesting to compare our metrics, since they are each based on
a different premise: the maximum flow metric is based on the
strength of the connection between source paper and sink paper, while
the authority metric is derived from the similarity of two
local neighbourhoods in the citation graph.
We chose CCIDF as our comparitive metric because it is a metric also
solely based on citation information, and because it is the metric
used by the {\sl ResearchIndex} database. 

For each of the fifteen papers in our test set, we used our algorithms
to retrieve the 10 most related papers according to the maximum flow
metric, the authority metric, and CCIDF.  In the computation of the
maximum flow metric, we used local citation graphs of 2.5 levels. For
the computation of the authority metric, we used local graphs of 1.5
level (this decision is discussed in Section \ref{bigsmall}).  For
CCIDF we used our global citation graph (a subgraph of the {\sl
ResearchIndex} citation graph) to compute the citation frequency of
each paper.  The results, based on the average precision results taken
over all fifteen test papers, are presented in a precision diagram in
Figure \ref{test2539}.

 \begin{figure}
 \epsfxsize =2.3in
\epsfysize =2.5in
%\centerline{\epsfbox{figNew/test2539.eps}}
\centerline{\epsfbox{figNew/NCompMetric.eps}}
 \caption{The test results of comparing different metrics}
 \label{test2539}
 \end{figure}

From the precision diagram we can conclude that our methods both give
highly accurate results. The high precision is quite remarkable, given
the fact that only information about the citation graph, not about the
content of the papers, is used in our methods. Moreover, our methods
both perform substantially better than CCIDF.

When analyzing our results, we found that one paper which was not
judged to be similar to the given test paper but which was nonetheless
given a high similarity rank by CCIDF contained more than 1000
references.  This points to a reason why CCIDF does not
give satisfactory results.  CCIDF is base only on the common
references between two papers.  If a papers has a long list of
references, it is very likely to have more papers in common with a given
test paper, and hence it will receive high CCIDF value.

{\tt This is where a paragraph should be added about the overlap
between the result sets obtained by different methods. To this
paragraph, remark can be added to the extent that our methods could be
combined to obtain the largest possible variety in retrieved papers.}


\subsection{Graph quality evaluation}
\label{GraphQualityTest}

The first factor that was found to influence our results is the
quality of the graph. Some nodes in our local citation graphs
correspond to papers for which the full paper, and hence also its
reference list, is not available in the database.  Such nodes are said
to be not {\sl fully parsed}.  The quality of a local citation graph,
in terms of its proportion of fully parsed nodes, will affect the
precision of our results.

In our experiments we ran the same algorithms with graphs of different
quality.  We found that the percentage of fully parsed nodes in the
first layer has the most influence on precision.  Some graphs have a
high percentage of fully parsed nodes in the whole graph, but still
give very bad results.  But all test results shows that a higher
percentage of fully parsed nodes in the first layer leads to better
results. The test results are shown in figure \ref{graphquality}. They
show clearly that the percentage of parsed nodes in the first layer
affects the precision of the result set. Based on our test, it appears
that at least $30\%$ of the nodes in the first layer should be fully
parsed in order to obtain dependable results.

 \begin{figure}
 \epsfxsize =2.3in
 \epsfysize =2.5in
 \centerline {\epsfbox{figNew/graphquality.eps}}
 \caption{Relation between graph quality and precision.
Here PPNFL means t 
Percentage of Parsed Nodes in the First Layer, OPPN means Overall Percentage
of Parsed Nodes.}
 \label{graphquality}
 \end{figure}


This test result indicates that our citation-based algorithms requires
deeper citation information that is obtained from the graph beyond the
first layer.  If the quality of the first layer is low, then the
remaining graph will also be limited in scope, and we cannot count on
our methods to retrieve useful information from it.  From another
perspective, if we find lots of nodes that are not fully parsed in the
first layer, it signals that the starting paper is on the fringe of
our database.  In other words, the paper is old or only tangentially
related to Computer Science, and hence many of its references are not
available in {\sl ResearchIndex}. Hence our citation-based metric can
not make good similarity judgment based on the data available.


\subsection{Parameter $d$ of the maximum flow metric}

As explained in Section \ref{weight}, the maximum flow metric depends
on the central parameter $d$. This parameter is used to set the
capacities of the edges and nodes for the flow calculation. 
In our experiment we tested the maximum flow metric for values of $d$
set to 50, 25, 12, 6, 3, 2 and 1.  We found that the precision drops 
with decreasing values of $d$.  This phenomena is shown in figure
\ref{flow2539_d}.  Based on our test, to get optimal precision $d$ should
be set to $25$ or greater. This confirms our discussion of Section
\ref{weight}, which asserts that $d$ should be around to the average
degree in the graph; the average degree in the citation graph is 38.

 \begin{figure}
 \epsfxsize =2.3in
\epsfysize =2.5in
%\centerline{\epsfbox{figNew/flow2539_d.eps}}
\centerline{\epsfbox{figNew/NCompD.eps}}
%\epsfbox{figures/graphquality.eps}
 \caption{Test results for the flow-based algorithm 
50, 25, 12, 6, 3 and 2.}
 \label{flow2539_d}
 \end{figure}

{\tt As I recall, the result sets for d=25 and d=50 were almost
identical. That could be mentioned here too. More general information
about the overlap between test results in general should be included, 
in the intro to section 5, or in the first subsection}

Recall from Section \ref{weight} that parameter $d$ expresses the
weight given by the maximum flow metric to longer paths between the
seed papers. The higher the value of $d$, the less the longer paths
will contribute to the maximum value of flow. If $d$ is chosen to be
extremely high (and assuming there is no direct link between the seed
papers, see Section \ref{direct}), then only paths of length two will
be counted, and our metric will be depend only on co-citation and
bibliographic coupling relationships, and `transitive citations' of
the form `source paper citing intermediate paper citing source paper'.

The value of $d$
also affects the place where the minimum cut arises. With higher values
of $d$, the capacity of the edges and nodes drops more quickly with
their distance from the seed papers.  If the value of $d$ if high, ,
then the minimum cut set will likely be further removed from the source
and sink paper, if it is low, then the minimum cut will likely occur
in the neighbourhood of the source or sink. 
If the cut set is close to the source or sink paper, then
the maximum flow value will be affected mainly by papers citing it
or papers cited by it.  But the reason for using the citation graph is to
discover deeper relationships between papers, so will want to go
deeper into the citation graph. 

When the $d$ is set to 1, then paths of all length are given equal
importance, and, by a well-known result from graph theory (see
e.g.~\cite{Diestel}), the minimum flow value equals the number of
disjoint paths (of any length) between source and sink. Intuitively, the equal
treatment of paths of all length does not lead to a good measure of
similarity. Our results confirm this. Analysis of several large
subgraphs of the citation graph of Computer Science literature (see ??? {\tt
cite Yuan's thesis}) shows that this graph is well-connected, and the
minimum cut between two nodes will almost always fall in the
neighbourhood of one of the two nodes. This was also confirmed by our
results for the case where $d=1$. 
As shown in figure \ref{testd1},
the maximum flow metric in this case depends almost completely on the
degree of the source or sink. As shown by the precision results, this
is an undesirable effect. 

 \begin{figure}
 \epsfxsize =2.3in
\epsfysize =2.5in
\centerline {\epsfbox{figNew/testd1.eps}}
 \caption{Comparing the degree of source with the maximum output value of the
flow-based metric}
 \label{testd1}
 \end{figure}
  

The results also indicate that in using the maximum flow metric the
parameter $d$ can be used as a tuning button to control the precision
and the scope of the result set.  We can let the end user choose different
values of $d$ to change the scope of the papers.  If $d$ is set to a
lower value, the algorithm may give a lower precision, but it can
return papers that are further away in the citation graph, which can
lead to finding related papers in a more general scope, and to the
retrieval of related papers that otherwise would be hard to find.  In
contrast, if a higher value of $d$ is chosen, we are likely to obtain
a better precision, but the returned papers will be close to the
source and sink papers, which likely confines the scope to a specific area.

            
\subsection{Size of graph in the authority metric}
\label{TestVector}

Our experiments with the authority metric showed that the size of the
local citation graph affects the results greatly. We tested two
alternatives: an authority vector derived from a local citation graph of
2.5 levels, referred to as a {\em big vector}, and an authority vector
based on a local graph of 1.5 levels, referred to as {\em small vector}.
We ran our experiments with both options and compared the results, in
order to see what size vector is best for representing the citation community.

The test results for comparing the results of the authority metric
based on big vector and small vector are shown
in the figure \ref{bigsmallvector2539}.

 \begin{figure}
 \epsfxsize =2.3in
\epsfysize =2.5in
%\centerline{\epsfbox{figNew/bigsmallvector2539.eps}}
\centerline{\epsfbox{figNew/NBigSmall.eps}}
 \caption{Test results of comparing the authority metric with big vector
and small vector}
 \label{bigsmallvector2539}
 \end{figure}

In terms of precision, small vector outperforms big vector. On the
other hand, we note that the percentage of direct link papers in small
vector result is extremely high, sometimes we obtain 100 percent direct
link papers.  Small vector tends to retrieve papers closer to the target
papers, whereas big vector tends to cover more deeply related papers.
We could let the end user to set the size of the vector or somehow combine
result from algorithms using different size of vector.  This will
enable us to get more informational results.
  
\subsection{The effect of a direct link}

In the result set
a from running our similarity algorithms, if one paper is citing or cited by
a seed paper, we say it is an direct link paper to the seed paper.  The
percentage of direct links is the percentage of direct link papers in
the result set. In this section, we compare the percentage of direct
links returned by the different metrics. 

A direct link between papers is the citing of one paper by another.
The importance of direct link has been noticed and studied in previous
research in library science literature.  Henry Small found that a very
effective predicator of strong co-citation linkages between papers is
provided by the direct citation patterns \cite{small1973}.  In our
research we also analyze the influence of direct link on our
similarity metric.  It is easy to see how the existence of a direct
link will affect both the values the maximum flow metric and the
authority metric.  For the maximum flow metric, if there is an direct
link between source and sink paper, it provides a shortcut with high
capacity between source and sink that can accomodate more flow.  For
the authority metric, graphs grown from two adjacent nodes will have a
larger intersection than those grown from nodes which are far apart.
So it is intuitive that we will obtain a certain percentage
of papers with a direct link to the seed paper in the result set.

We test the maximum flow and the authority metric in terms of the
percentage of direct link paper in the result set.  The results are
shown in figure \ref{DLToTotal}.  The test result verifies that all of
these three algorithms retrieve a certain percentage of direct link
papers, and it also shows the importance of direct link papers in
similarity computation.

 \begin{figure}
 \epsfxsize =2.3in
\epsfysize =2.5in
\centerline{\epsfbox{figNew/DL2539.eps}}
 \caption{Percentage of directly linked papers in the result set}
 \label{DLToTotal}
 \end{figure}    

We also experimented with small adjustments to our algorithms in terms
of direct link.  For the maximum flow metric, we performed some tests
changing the capacity of the direct link, while leaving the capacities
of all other edges the same. Our findings were as
expected, namely that we obtain more direct link papers
with a higher capacity of the direct link. 

For the authority metric, we modified the way in which we grow the
local citation graph. Namely, if two seed papers are connected by a
direct link, then all nodes in layer 1 of the first graph will be
included in layer 2 of the second graph, and vice versa. Hence we
modified the algorithm so as not to use direct link information in the
process of growing local citation graph. We found that this affects
the percentage of direct link papers very little. This result
indicates that when there is a direct link between papers, their local
citation graphs have a large overlap even if the direct link itself is
discarded. 

As a conclusion for above experiments, we do find that a direct link
or direct citation between papers is greatly influences the similarity
evaluation.  A direct link between seed papers has greater impact on
the maximum flow metric than on the authority metric. However, for the
maximum flow metric we can leverage this influence by adjusting the
capacity weight of the direct link in the flow computation.  The
authority metric is quite stable and tends to retrieve papers which
have a similar citation community rather than just a direct citation
relationship.  For the maximum flow metric, one could let the user 
adjust the capacity of the direct link to represent how much they trust
direct links in similarity computation.  If the user wants to dig out deeper
similarity relationships they need to give the direct link a lower capacity,
otherwise they must give it a higher capacity.


\section{Future Work}
\label{future}


In the future, we may want to take more detailed citation information
into account. One direction for future work is to assign weights to
the citations made in an article. Namely, citations made in the same
paper have a different importance to the author or research.  We might
assign different weights to references in terms of where they appear
(introduction, body) and how often they appear in the research paper
as opposed to treating all the references equally.  

In scientific papers some referenced papers are cited together in one
square bracket.  In that case those papers must have something in
common from a scientific research point of view. How to take advantage
of this subtle hint is another open issue in our research.  Maybe we
can treat those papers as one paper somehow; in that way we can
simplify the graph to some degree. Another option is to build paths
among those papers to reflect this special relationship.

One drawback of using more detailed citation information is that we
need to analyze the context of each citation instance.  Although it is
possible to query the database to obtain the citation context, it will
greatly slow down the computation.  This prevented us from
investigating this option in the present work, and we leave it to
future research.  In the future we can find out such information and
do more extensive preprocessing on our graph.  

Another option for future research is to treat co-citation and reference
coupling differently in computing the similarity, by assigning weights to
different edges using directed graph.  In our current research we do not
consider the direction and treat co-citation and bibliographic coupling
equally.  Depending how much you trust each of these two relationship in
judging relatedness, one could set up an adjustable parameter
to leverage the similarity judgment.

Also some interesting work needs to be done to combine text-based metric and
link-based metric.  One simple way is just use a weighted sum of each
individual similarity measure to compute similarity.  Another option is to
use text methods to simplify the citation graph to highlight important
citations.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Conclusions}

In our research, we want to find an efficient way to judge relatedness
among research papers using only the citation graph.  One assumption
for doing that is that if two research papers are related from scientific
research point of view, the information conveying the relationship between them
should be found in the citation graph.  Another premise is that
reference coupling and co-citation do reflect similarity and
relatedness between papers.  The maximum flow  algorithm can be used to find
out how strongly each pair of papers is connected in the citation graph;
the authority metric measures the similarity of the local
neighborhood of two papers in the citation community.  From the test
results, both metrics are promising and efficient in finding related
papers for scientific research.  In the real world, it also means the
by using the citation index we
can retrieve similar papers much faster than by full text analysis.

%%%%%%%%%%%
%\section{Acknowledgement}
\vspace{4mm}

\noindent
{\Large\bf Acknowledgements}

\vspace{4mm}

\noindent
I would like to thank Dr. Steve Lawrence from NEC Research
Laboratories for providing computer science citation information and
for allowing access to the {\sl ResearchIndex} Database for our robot.


\vspace{4mm}

\noindent
{\Large\bf About the Author}

\vspace{4mm}

\noindent

{\em Wangzhong Lu} is pursuing a Master's degree of Computer Science at
Dalhousie University.  His research interests are in the fields of software
agents and similarity measure of information entities.  He can be reached by
e-mail: {\tt luwz@cs.dal.ca}.

{\em Jeannette Janssen} is Assistant Professor of the Department of
Mathematics and Statistics, Dalhousie University. Her current research
interests are Combinatorial Optimization, Graph Colouring, Frequency
Assignment.  She can be reached by e-mail: {\tt janssen@mscs.dal.ca}.

{\em Evangelos E. Milios} is Professor and Director of the Graduate Program
of the Faculty of Computer Science, Dalhousie University. His current
research activity is centered on Software agents for Web information
retrieval. He can be reached by e-mail: {\tt eem@cs.dal.ca}.

{\em Nathalie Japkowicz} is Professor of the School of Information Technology
and Engineering, University of Ottawa. Her research interests are in the area
of Artificial Intelligence and, most specifically, Machine Learning, Neural
Networks and Natural Language Processing. She can be reached at {\tt
nat@site.uottawa.ca}.

%\bibliographystyle{alpha}
\bibliographystyle{plain}
%%\bibliographystyle{unsrt}

\bibliography{drea}

%\newpage
%The End.


\end{document}


