%%%%%%%%%%%%%%%%%%%%% the latest citation_graph.tex %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\input epsf
\documentstyle[twocolumn]{article}
%****************************************************************
%pagestyle{empty}
%****************************************************************

\textheight 8.5in
\textwidth 6.0in
\columnsep 0.37in
\oddsidemargin 0.25in   
\evensidemargin 0.25in
\topmargin -.3in   
\headheight 0in   
\footheight 1in
\hyphenation{C-G-C-S-L}

\long\def\invis#1{}

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

\title{
Characterizing and Mining Citation Graph of Computer Science Literature
}

\author{Yuan An \\
        \mbox{} \\
        Faculty of Computer Science, Dalhousie University \\
        \mbox{}\\
        \and
        Jeannette Janssen \\
        \mbox{} \\
        Department of Mathematics and Statistics, Dalhousie University \\
        \mbox{} \\
        \and
        Evangelos E. Milios \\
        \mbox{}\\
        Faculty of Computer Science, Dalhousie University \\
        \vspace{2cm}
        \mbox{}
}

\date{June, 2001}

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

\begin{document}

%***************************************************************
\newcommand{\cascon}{{CASCON}}


%***************************************************************
\bibliographystyle{plain}

\maketitle
%***************************************************************
%\thispagestyle{empty}
%***************************************************************

%***************************************************************
%*Abstract
%***************************************************************
\begin{abstract}

Citation graphs representing a body of scientific literature convey measures
of scholarly activity and productivity. In this work we present a study of the
structure of the citation graph of computer science literature.  Using a web
robot we build several citation graphs from parts of the digital library
{\sl ResearchIndex}. After verifying that the degree distributions follow a
power law, we apply a series of graph theoretical algorithms to elicit an
aggregate picture of the citation graph in terms of its connectivity.

\end{abstract}

%********************************************************************
%*Introduction
%********************************************************************
\section{Introduction}
\label{sec:introduction}

%A Citation Graph of a scholarly area is a networked information space that can
%be represented as a directed graph whose nodes are the articles and whose
%edges are references that appear in the node of origin.

A body of scientific literature can be seen as a networked information space,
a collection of information entities connected by a link structure. Here the
information entities are the scientific papers, and they are linked together
by citation relations. The link structure of this networked information space
can be represented by a directed graph, which is commonly referred to as the
{\sl citation graph}. Each node of the citation graph represents a paper, and
a directed link from one node to another implies that the paper associated
with the first node cites the paper associated with the second node.

Citation graphs representing scientific papers contain valuable information
about levels of scholarly activity and provide measures of academic
productivity. A citation graph has the potential of revealing interesting
information about a particular scholarly research: it may be possible
to infer research areas and their evolution over time, measure relations
between research areas and trace the influence of ideas that appear in the
literature. 

In this article we report the results of examining various aspects of
connectivity of the citation graph of computer science literature with graph
theoretic algorithms.  To build the citation graph, we implemented a web robot
to query the online computer science library {\it ResearchIndex}. We
built the citation graph for three different areas within computer science:
Neural Networks, Software Engineering and Automata. The areas were chosen to
be distinct from each other, and to contain one area (Neural Networks)
familiar to the authors.

We first confirmed the power law for the in-degree distribution discovered by
other studies on citation information of science literature. Next we
investigated the connectivity of the citation graph by applying a series of
graph theoretic algorithms to compute the weakly connected
components, strongly connected components and biconnected components. In an
attempt to separate areas, we further computed the global minimum cut, and the
minimum cuts between authority papers in different areas. We also computed the
shortest paths between pairs of papers. An aggregate picture of the citation
graph in terms of its connectivity emerges out of the results.

The following considerations motivated our study. Understanding the link
topology of the citation graph using graph-theoretic tools may:
\begin{enumerate}
\item
yield valuable insight into other citation or co-citation analyses. {\tt jj:
  what is meant here? Maybe clarify}
\item
facilitate knowledge discovery relying on link information such as
similarity calculation, and finding communities.
\item
help in citation graph visualization.
\item
help evaluate the evolution of specialties or research themes over time.
\end{enumerate}

%***********************************************************************
%*Main results
%***********************************************************************
\subsection{Main results}
\label{subsec:mainresults}

We performed three sets of experiments on our collection of citation graphs
obtained from different research areas. The main result of our analysis was
that these citation graphs showed remarkably similar behaviour in each of our
experiments. Moreover, the results of the experiments performed on the union
of the three graphs was again similar to that of each of its parts, indicating
the self-similarity of the citation graph.

We first constructed a robot for querying {\it ResearchIndex}
\cite{citeseer2001}, and using the robot we built a collection of three local
citation graphs by starting with papers from three different topics.  We also
merged the three graphs into the union graph: the combined citation graph of
the three individual ones.

The first set of experiments computed the in-degree distributions and
demonstrated that they follow a power law. Specifically,
the fraction of articles with k citations is proportional to $1/k^{e}$, where
the exponent $e$ is close to 1.7 for each of the four graphs.

{\tt jj: is the above change justified?}

The second set of experiments investigated the connectivity of the citation
graph. It was found that approximately $90\%$ of the nodes form a single
Weakly Connected Component (WCC) if citations are treated as undirected edges.
Within this giant WCC, almost 68.5\% of the nodes have no incoming link,
suggesting that 68.5\% of the publications in the giant WCC have not been
cited (yet). See Figure~\ref{structure1} for a representation of this result.
Furthermore, within the giant WCC, around 58\% of its publications form a
large Biconnected Component(BCC), and almost all the remaining nodes of the
giant WCC fall into trivial BCCs, each of which consists of a single distinct
node. The aggregate picture that emerges is shown in Figure~\ref{structure2}.

\begin{figure}[htbp] 
\epsfxsize=2.75in
\epsfysize=1.5in 
\vspace{0.2cm} 
\epsfbox{figures/structure1.eps} 
\caption{The connectivity of the citation graph:68.5\% of the nodes have no
incoming link.}
\label{structure1} 
\end{figure}

\begin{figure}[htbp] 
\epsfxsize=2.75in
\epsfysize=1.5in 
\vspace{0.2cm} 
\epsfbox{figures/structure2.eps} 
\caption{The connectivity of the citation graph: 58\% of the nodes in the
giant Weakly Connected Component(WCC) account for a big Biconnected
Component(BCC).}  
\label{structure2} 
\end{figure}

The third set of experiments applied the Minimum cut Maximum flow algorithm
for finding cluster information. The results indicated that we need more
sophisticated tools for the clustering problem in the citation graph.

%*****************************************************************
%*Related work
%*****************************************************************
\subsection{Related work}
\label{subsec:related}

Research in bibliometrics has long been concerned with the use of citations
to produce quantitative estimates of the importance and impact of individual
scientific publication and journals. The best-known measure in this
field is Garfield's impact factor \cite{garfield1972}. 
The impact factor is a ranking scheme based fundamentally on a pure counting
of the in-degree of nodes in the citation graph.  Redner \cite{redner1998}
has focused on the statistical distribution of the number of citations of the
scientific literature. Chen \cite{chen1999,chen2001} developed a set of
methods that extends and transforms traditional author co-citation analysis
by heuristically extracting structural patterns from scientific literature
for visualization as a 3D virtual map.

As to structural analysis of large scale networks, Broder et al.~\cite{broder2000} studied various properties of Web graph including its
diameter, degree distributions, connected components, and macroscopic
structure, proposing a bow tie model of the Web. Earlier work, exploring
the scaling properties of the Web graph, has been done by Barabasi
\cite{barabasi1999}.

Exploiting the link topology of large scale networks for information discovery
has been recently proposed for the Web \cite{chakrabarti1999}.  However, since
the scientific citation graph and the Web graph are governed by different
principles, our analysis of the link topology of citation graphs deals with
different types of problems than those that arise in the Web--specifically, the partitioning of such structure into sparsely
inter-connected pieces--and we approach this through an interesting
combinatorial technique.

{\tt jj: I don't really understand the above sentence}

%****************************************************************
%*Measurements
%****************************************************************
 
\section{Measurements on the Citation Graph}
\label{sec:measurements}

The first step is to extract citation graphs from a citation database. {\it
ResearchIndex}\cite{citeseer2001} is a Web-based digital library and citation
database of computer science literature and provides us easy access to
citation information for our study. We constructed a Web robot for querying
{\it ResearchIndex} autonomously. We chose three areas within computer
science as starting points: {\it Neural Networks,
Automata and Software Engineering}. 

Our procedure for creating the citation graphs started from a base set,
obtained via keyword search, containing thousands of nodes that are not
necessarily connected. We then expanded this base set by following incoming
links and outgoing links of the nodes in the base set. 
Due to time and space limitations, the crawling process is terminated when
there are about 100,000 papers parsed for each topic.

{\tt jj: What was the criterion for stopping the building process? When 100,000
  papers were reached, or when Yuan ran out of space? As it is stated it looks
  funny, as if there was a switch in a program telling it to stop when you
  have "about" 100,000 papers.}

The above process leads to the formation of three raw citation graphs for
each of the selected topics and their  union graph.
We note that there are two types of articles in the raw citation graphs: the
first type of article is fully available in {\it ResearchIndex}, including
its full text and references; the second type of article is brought into {\it
ResearchIndex} by a reference of other papers, but its text and references are 
not in {\it ResearchIndex}. The second type only contributes part of the
information to the citation graph.
In the experiments reported in this article, the citation graphs used were
obtained from the raw citation graphs by removing all articles of the second
type.
The measurements we extracted from the citation graphs we built included
in- and out-degree distributions (involving only the articles in the citation
graphs, which are a subset of the citing and cited articles respectively) and
diameters.

\subsection {Degree distributions}

We begin by considering the in-degrees of nodes in the citation graph. We
observed that the in-degree distributions follow a power law; i.e.~the
fraction of papers with in-degree $i$ is proportional to $1/i^{\gamma}$ for
some $\gamma >1$.  Our experiments on all citation graphs built from the
different topics as well as the union citation graph confirmed this result at
a variety of scales. In all these experiments, the value of the exponent
$\gamma$ in the power law for in-degrees is a remarkably consistent 1.71.

{\tt jj: maybe 1.7? Is it really always that close to 1.71?}

Figure~\ref{indegreebin} is a log-log plot of the binned in-degree
distribution of the union citation graph for extracting the exponent $\gamma$.
The value $\gamma =1.71$ is derived from the slope of the line providing the
best linear fit to the data in the figure.

\begin{figure}[htbp]
\epsfxsize=2.75in
\epsfysize=1.5in
\epsfbox{figures/inlog.eps}
\caption{The in-degree distribution in the union citation graph in
computer science literature subscribe to the power law with exponent=1.71.}
\label{indegreebin}
\end{figure}

In our study of the degrees, we concentrated on the in-degree, because
citations must be acquired, so in-degree can vary over time, and the process
is out of the control of the author of the paper. There is reason to assume
that this acquisition process is of the type that naturally leads to power law
distributions. The out-degree of a paper in the citation graph represents the
number of references of the paper, and hence depends only on one decision by
the paper's author. Moreover, the out-degree information in our graphs in
incomplete, since we do not count the papers that are not present in the {\it
  ResearchIndex} database. This affects older papers more, since their
references are less likely to be available in electronic form. Therefore, the
out-degree distribution of our graph is less informative, and we have not
considered it in our experiments. 

{\tt jj: Do you agree with these changes? Maybe include some stats on
  out-degree, such as average, min, max?}

\subsection {Diameter}

We turn next to the diameter measurement of citation graphs. In this study,
the diameter is defined as the maximum over all ordered pairs($u,v$) of the
length of the shortest path from $u$ to $v$ in the citation graph. We
measured two types of diameter for the citation graph: directed diameter and
undirected diameter. Directed diameter is measured by the directed shortest
path or dipath, while undirected diameter is obtained by treating edges as
undirected.

Before we measured diameters, we tested the connectivity of the citation graph
as an undirected graph. The results revealed that the citation graph is not
connected. This means that there are nodes which cannot be reached by a path
from other nodes, implying that the diameter is infinite. However, the tests
also revealed that $\approx 80\%-90\%$ of the nodes are in one giant connected
component, while the rest form a few very small components. Details are
described in Section~\ref{sec:reachability}.  We therefore considered the
diameter of this giant connected component as the undirected diameter of the
graph.
  
THe diameters obtained by applying Dijkstra's shortest path algorithm on the
giant connected components of the citation graphs built for the three topics
and their union are shown in
Table~\ref{tableofdiameters}.

\begin{table*}[htbp]
\begin{center}
\begin{tabular}{|l|l|l|l|} \hline
      & graph  & directed & undirected \\
      & size & diameter  & diameter \\ \hline
citation graph--N.N.     & 23,371 & 24      & 18         \\ \hline
citation graph--Automata & 28,168 & 33      & 19           \\ \hline
citation graph--S.E.     & 19,018 & 22      & 16            \\ \hline
union citation graph     & 57,239 & 37      & 19             \\ \hline
average                  &        & 29      & 18             \\ \hline
\end{tabular}
\end{center}
\caption{The diameters of citation graphs built from different topics as well
as union citation graph. Topic: N.N.: Neural Networks, S.E.: Software
Engineering.}
\label{tableofdiameters}
\end{table*}

Ignoring the orientation of edges, we observe that the
citation graph is a `small world' with an undirected diameter of around
18. The result is consistent at a variety of scales and topics. 

In contrast, we do not obtain such a `small world' property in the {\em
directed} citation graph. Our statistical study shows that the probability
of having a directed path between any pair of nodes is only {\em 2\%}.  The
directed diameter was calculated by taking the maximum only over those pairs
of nodes that are connected by a directed path. This diameter turned out to be
around 30 (see Table \ref{tableofdiameters}).  This is an outcome of the
temporal nature of the citation graph.  In almost all cases, references can
only be made to papers that appeared previously, and therefore directed cycles
are unlikely. (Some directed cycles arise in special circumstances, see
Section \ref{scc})

%*******************************************************************
%*Components
%*******************************************************************

\section {Reachability and Connected Components}
\label{sec:reachability}

We now consider the connectivity of our citation graphs of computer science
literature. This involves examining the various types of its connected
components and reachability of nodes. Given a citation graph $G=(V,E)$, we
will view $G$ both as a directed graph as well as and undirected graph (the
latter by ignoring the direction of all edges). We now ask how well connected
the citation graph is. We apply a set of algorithms that compute reachability
information and structural information of directed and undirected citation
graphs: {\it Weakly Connected Components (WCC), Strongly Connected Components
  (SCC)} and {\it Biconnected Components (BCC)}.

%*******************************************************************
%*WCC
%*******************************************************************
\subsection {Weakly connected components}
\label{subsubsec:wcc}

Mathematically, a {\it Weakly Connected Component(WCC)} of an undirected graph
$G=(V,E)$ is a maximal connected subgraph of $G$. A WCC of a citation graph is
a maximal set of articles each of which is reachable from any other if links
may be followed either forwards or backwards. In the context of a citation
graph, links stand for the citations from one article to other articles cited
in the former one. The WCC structure of a citation graph gives us an aggregate
picture of groups of articles that are loosely related to each other.
 
The results drawn from the weakly connected component experiments on citation
graphs are shown in Table~\ref{tablewcc}. The results reveal that the
citation graph is well connected--a significant constant fraction
$\approx 80\%-90\%$ of all nodes fall into one giant
connected component. 
 It is remarkable that the same general results on connectivity are
observed in each of the three topic subgraphs. In turn, the same behavior
is observed for the union graph, suggesting a certain degree of
self-similarity.

\begin{table*}[htbp]
\begin{center}
\begin{tabular}{|l|l|l|l|l|} \hline
      & graph & size of largest & percentage of & size of second \\ 
      & size  & WCC & largest WCC & largest WCC \\ \hline
citation graph--N.N.     & 23,371 & 18,603      & 79.6\% & 21   \\ \hline
citation graph--Automata & 28,168 & 25,922      & 92\%   & 20     \\ \hline
citation graph--S.E.     & 19,018 & 16,723      & 87.9\% & 12      \\ \hline
union citation graph     & 57,239 & 50,228      & 87.8\% & 21       \\ \hline
\end{tabular}
\end{center}
\caption{The results of Weakly Connected Component experiments on different
citation graphs: the majority ($\approx 90\%$) of articles are connected to
each other if links are treated as without directions.citation graph:N.N
stands for Neural Networks; S.E. stands for Software Engineering.}
\label{tablewcc}
\end{table*}

%*******************************************************************
%*SCC
%*******************************************************************
\subsection{Strongly connected components}
\label{subsec:scc}

We turn next to the extraction of {\it Strongly Connected Component(SCC)} of
the connected components of the three topical citation graphs and their union
graph.  A {\it Strongly Connected Component(SCC)} of a directed graph is a
maximal subgraph such that for all pairs of vertices $(u,v)$ of the subgraph,
there exists a directed path (dipath) from $u$ to $v$. In the context of the
citation graph, a dipath from $u$ to $v$ means that article $u$ directly
cites article $v$ or article $u$ cites a intermediate article $w$, $w$ cites
next intermediate article and so on, until it reaches article $v$
indirectly. Since there is a temporal direction between citing article and
cited article, if article $u$ directly or indirectly cites article $v$, then
$v$ would not cite back to $u$.
 As a result, we might expect that there is no SCC in the citation graph. But
contrary to our expectation, the results of SCC experiments on the collection
of citation graphs reveal that there exist one to three sizable SCC's in each
of the citation graphs, as well as a few very small SCC's.
 The results drawn from the experiments are shown in Table~\ref{tablescc}.

\begin{table*}[htbp]
\begin{center}
\begin{tabular}{|l|l|l|l|l|} \hline
      & graph & size of largest & size of second & size of third \\ 
      & size  & SCC & largest SCC & largest SCC \\ \hline
citation graph--N.N.     & 18,603      & 144 & 14  & 10 \\ \hline
citation graph--Automata & 25,922      & 192 & 29  & 24   \\ \hline
citation graph--S.E.     & 16,723      & 17  & 11  & 8    \\ \hline
union citation graph     & 50,228      & 239 & 155 & 60      \\ \hline
\end{tabular}
\end{center}
\caption{The results of Strongly Connected Component experiments on different
citation graphs: there exist many small SCCs, among them there are one -three
bigger SCC(s), the rest are even smaller comparing those bigger
ones. citation graph:N.N stands for Neural Networks; S.E. stands for Software
Engineering.} 
\label{tablescc}
\end{table*}

In order to know which publications formed the SCCs, i.e. how the directed
cycles were generated in those citation graphs, we extracted some SCCs from
citation graphs and searched articles of these SCCs directly in {\it
  ResearchIndex}'s database to find their titles, abstracts, authors, journals
and published years. Our study shows that several types of publications formed
SCCs: 
(1) publications written by same authors tend to cite each other, they
usually produce self-citations, 
(2) publications which are tightly relevant
tend to cite each other, e.g., publications, whose authors in same institute,
dealing with same specialty and getting published concurrently are highly
relevant and tend to cite each other, 
(3) publications which were published in
several different forms, such as journals, conference proceedings or technical
reports, at different times often formed directed cycles with other
publications.  The different forms of the publication were considered as one 
node during our creation process of the citation graph.  
(4) books or other publications which were
published in several editions at different times, where the newer editions
contained more recent references, often acted as jump points in
the citation graph. 
The jump points formed by publications of type (4) caused large directed
cycles in the citation graph; this is the reason of the existence of one to
three bigger SCCs.
Types (1) - (3) of articles usually gave rise only to small SCCs
containing 2-5 articles.

A conceptual map arising from the analysis of the results of the SCC experiment
on the union citation graph is depicted in Figure~\ref{sccpicture}. A number
of small SCCs are embedded in a well connected background net.  This
background net is a directed acyclic structure, i.e., there is no directed
cycle in the background net.  

\begin{figure}[htbp] 
\epsfxsize=2.25in
\epsfysize=1.5in 
\center{\epsfbox{figures/scc.eps}} 
\vspace{-0.5cm}
\caption{The directed connectivity of a citation graph: a number of small SCCs embedded
in a background net;the background net is a directed acyclic graph.}
\label{sccpicture} 
\end{figure}

%********************************************************************
%*BCC
%********************************************************************       
\subsection {Biconnected components}
\label{subsubsec:bcc}

We now turn to a stronger notion of connectivity in the undirected view of the
citation graph, that of biconnectivity.  A {\it Biconnected Component(BCC)} of
an undirected graph is a maximal subgraph such that every pair of vertices is
biconnected. Two vertices $u$ and $v$ are biconnected if there are at least
two disjoint paths between $u$ and $v$, or, equivalently, if $u$ and $v$ lie
on a common cycle.  Any biconnected component must therefore lie within a
weakly connected component. Applying the biconnected component algorithm on
the giant connected components of citation graphs, we find that each giant
connected component of each citation graph contains a giant biconnected
component. The giant BCC acts as a central biconnected nucleus, with small
BCCs connected to this nucleus by cut vertices, and other single trivial nodes
connected to the nucleus or a small BCC.

The numerical analysis of sizes of BCCs indicated that $\approx 58\%$ of all
nodes account for the giant biconnected nucleus, the rest $\approx 40\%$ of
the nodes are in trivial BCCs each of which consists of single distinct node,
and the remaining $\approx 2\%$ of the nodes fall into a few small BCCs.

%*****************************************************************
%*Aggregate
%*****************************************************************
\subsection {Aggregate picture}
\label{subsubsec:aggregate}

From the application of algorithms to detect connected components
algorithms, an aggregate picture of the citation graph as an
undirected graph emerged. First of all, the citation graph is not, in
general, connected. This can be explained in the context of our
construction of thecitation graphs: we started building each citation
graph from a base set containing a number of documents which are not
necessarily connected, and while the expansion of the base set serves
to connect many of these documents, others remain in small isolated
components. Moreover, our cleaning up process of removing those
articles, whose text and references are not available, produced more
isolated components.  Secondly, the results of WCC experiment indicate
that $\approx 90\%$ of the nodes form a giant weakly connected
component. The single giant WCC can be divided into two parts:
one part contains almost 68.5\% of the nodes without any incoming
link, suggesting that 68.5\% of publications have not been cited yet,
another part contains the rest of publications with at least one
citation. Finally, in the giant WCC, around 58\% of nodes form a
big Biconnected Component(BCC) act as a biconnected nucleus, with a
few small BCCs connected to this nucleus by cut vertices, and all rest
of nodes fall into trivial BCCs each of which consists of single
distinct node connected to this nucleus or some other small
pieces. The aggregate picture is shown in Figure
\ref{structure1} and Figure~\ref{structure2}.
 
%*****************************************************************
%*Connectivity
%*****************************************************************
\section {Does connectivity depend on some key articles?}
\label{subsec:contribution}

We have observed that the citation graph is well connected--90\% of
the nodes form a giant connected component which in turn contains a
biconnected nucleus with 58\% of all nodes. The result that the in-
distributions follow a power law indicates that there are a few nodes
of large in-degree. Moreover, our analysis of the out-degrees implies
that there are also some nodes with large out-degree. We are
interested in determining whether the widespread connectivity of the
citation graph results from a few nodes of large in-degree acting as
``authorities'' or a few nodes of large out-degree acting as ``hubs''.
We test this connectivity by removing those nodes with large in-degree
or out-degree, and computing again the size of the largest WCC.  The
results are shown in Table~\ref{tablewhole1} and Table~\ref{tablewhole2}.

\begin{table*}[htbp]
\begin{center}
\begin{tabular}{|c|l|l|l|l|l|l|l|l|} \hline
 size of graph & \multicolumn{8}{c|}{50,228} \\ \hline 
$k$ &  200 & 150  & 100 & 50 & 10 & 5 & 4 & 3 \\ \hline
size of largest & 50,107   & 49,990  & 48,973  & 43,073  & 26,098  & 14,677
& 9,963  & 1,140   \\ 
WCC & & & & & & & & \\ \hline
\end{tabular}
\end{center}
\caption{Sizes of the largest Weakly Connected Components(WCCs) when nodes
with in-degree at least $k$ are removed from the giant connected component of
union citation graph}
\label{tablewhole1}
\end{table*}
\begin{table*}[htbp]
\begin{center}
\begin{tabular}{|c|l|l|l|l|l|l|l|l|} \hline
 size of graph & \multicolumn{8}{c|}{50,228} \\ \hline 
$k$ &  200 & 150  & 100 & 50 & 10 & 5 & 4 & 3 \\ \hline
size of largest & 50,202 & 50,202 & 50,198 & 50,131  & 46,092  & 37,556 &
33,279 & 26,489   \\ 
WCC & & & & & & & & \\ \hline
\end{tabular}
\end{center}
\caption{Sizes of the largest Weakly Connected Components(WCCs) when nodes
with out-degree at least $k$ are removed from the giant connected component of
union citation graph}
\label{tablewhole2}
\end{table*}

{\tt jj: It would be good to incorporate Nur's comments here: namely, also give the size of the graph after the nodes with large degree have been removed. In other words, how large is the giant WCC with respect to the remaining graph. Can we still do this computation, i.e. are the graphs still stored somewhere?}

These results show that the widespread connectivity does not depend on either
hubs or authority papers. Indeed, even if all links to nodes with in-degree 5
or higher are removed (certainly including links to every well-known article
on computer science), the graph still contains a giant Weakly Connected
Component(WCC). Similarly, if all links to nodes with out-degree 3 or higher
are removed, the graph is still well connected.  We conclude that the
connectivity of citation graph is extremely resilient and is not due to the
existence of hubs and authorities, which are embedded in a graph that is well
connected without their contributions.

%********************************************************************
%*Min-cut and Max-flow
%********************************************************************
\section{Minimum cuts}
\label{sec:cuts}

A question related to understanding the structure of the citation graph is
that of finding thematically cohesive communities. So far, our study of various
types of connected components has resulted in a well-connected citation graph
with a giant biconnected nucleus. The next question is whether there is any
further structure within this nucleus. We attack this problem using minimum
cut algorithms, both for global minimum cut and for minimum cuts between
specific pairs of nodes.
   
Mathematically, an (edge) cut $C$ of graph $H=(V,E)$ is a set of edges which,
when removed, disconnect the graph. The size of a cut is the number of edges
in the cut. Given an edge weight function $w:E\rightarrow R$, a minimum cut
is a cut whose total weight is minimum.

Our min-cut experiments focus on the giant connected component of union
citation graph. After extracting the giant connected component $H=(V,E)$ from
the union citation graph, we assign edge weight $w(e)=1$ for all $e\in
E$, and then apply the global minimum cut algorithm on $H$. In order to explore
the interior structure of graph $H$, we implemented the min-cut exploratory
procedure as below:

{\tt
1. procedure Explore\_Min\_Cut($H= \\
2. \hfill (V,E)$)\\
3. \hspace{0.1cm} while $|H|>0$\\
4. \hspace{0.6cm} compute min-cut $C$ of $H$;\\
5. \hspace{0.6cm} calculate edge weight over \\
6. \hfill crossing edge set $F$;\\
7. \hspace{0.6cm} let $H_{1}=(C, E_{1})$ be graph \\
8. \hfill induced by $C$;\\
9. \hspace{0.6cm} let $H_{2}=(V-C, E_{2})$ be graph \\
10. \hfill induced by $V-C$;\\
11. \hspace{0.6cm} Explore\_Min\_Cut($H_{1}$);\\
12. \hspace{0.6cm} Explore\_Min\_Cut($H_{2}$);\\
13. \hspace{0.1cm} end while;\\
}   

Most of the resulting cuts found by the above procedure are trivial cuts,
each of which separates only one node from the rest of the graph.

 When the procedure {\it Explore\_Min\_Cut(H)} is applied to graph $H$
recursively until the fragments become trivially small, we find that 
99\% of the cuts are trivial.

From these experiments we conclude that the interior link structure of
the citation graph is dense; There is {\em no} explicit community
information discernible through global minimum cuts. We conclude that	
we need more sophisticated tools for finding communities in citation
graph.

Since the global minimum cut approach does not give us communities, we turn
to the computation of minimum cuts between specific nodes. If two nodes are
selected to belong to different topics, then possibly the minimum cut between
them might separate the papers belonging to the two topics.  To investigate
this hypothesis we selected authority papers (papers with large in-degree)
belonging to the topics of Neural Networks, Automata and Software
Engineering, and computed the minimum cuts of the union graph between
pairs of authority papers.  For the minimum cut computation, we made two
modifications to the (directed) union graph of 50,228 nodes:

1. We added the reverse edges to all the edges of the graph, so as to
effectively treat it as an undirected graph.

2. We added node capacities equal to 1, by the following construction.  We
replace each node $v$ by two nodes $v_{in}$ and $v_{out}$ and an edge from
$v_{in}$ to $v_{out}$, and we connect all the edges into $v$ to $v_{in}$ and
all the edges out of $v$ to $v_{out}$. All edges have capacity 1, thus
allowing us to associate capacities 1 to all the nodes, as well.

The resulting graph has 100,456 nodes.

From these experiments we obtain highly unbalanced partitions of the union
graph. The cut sizes are similar to the in-degree of the nodes, and the
smaller partition contains at most a few hundred nodes while the larger
partition contains the rest of the nodes (approximately 99,000).


%*******************************************************
%*Conclusions
%*******************************************************
\section{Conclusion}
\label{sec:conclusions}

The Citation Graph of Computer Science is a directed graph whose nodes are
articles and whose edges are references that appear in the node of origin.
The citation graph can potentially be used in a variety of ways, for example
to infer research areas and their evolution over time, measure relations
between research areas, and trace the influence of ideas that appear in the
literature. 
 In this article, we reported the results of examining the citation graph
with graph theoretic algorithms.  We constructed a web robot querying the
computer science digital library {\it ResearchIndex} and built the citation
graph for three different areas within computer science.
 We verified that the in-degree distribution follows the power law, and we
applied a series of graph theoretic algorithms. We extracted Weakly Connected
Components, Strongly Connected Components, Biconnected Components, and we
computed Global Minimum Cut, Minimum cuts between authority papers in
different areas, and shortest paths between pairs of papers. Based on the the
results, we elicit an aggregate picture of the citation graph in terms of its
connectivity. Our attempts to extract research communities with the above
standard graph theoretic algorithms and no further heuristics were not
successful. The citation graph retained a large well connected component,
pointing to the need for the application of more sophisticated balanced graph
partitioning algorithms. It should be pointed out that the balanced graph
partitioning problem is NP-hard \cite{garey1976}, but local search strategies
have been proposed for them \cite{kernighan70efficient,
fiduccia82lineartime}.

A number of interesting further directions of research are suggested
by our study. For example, fundamental questions about the evolution
of the citation graph should be addressed. A future study in this
direction should involve both the evolution of the in-degree of
individual articles and the evolution of the link topology of the
graph.  A study of the evolution of the local link structure of
citation graphs can be used for predicting research trends or for
studying the life span of specialties and communities.  The challenge
is to develop more sophisticated tools to study the evolution of the
link structure, since performing a hubs-and-authorities analysis on
the citation graph is difficult due to the graph's size.

Finally, we believe that characterizing the link topology of scientific
citation graph has the potential to benefit a number of areas, such as
information retrieval. How can we annotate autonomously the communities
discovered by graph partitioning process without human intervention? 

{\tt jj: These last two paragraphs are somewhat vague. Do we want to
say more here, or be more specific?}

%******************************************************************
%*About the Authors
%******************************************************************
\vspace{4mm}
\noindent
{\Large\bf About the Authors}
\vspace{4mm}
\noindent

{\em Yuan An} is Graduate Student of Master's Program in Faculty of Computer
Science of Dalhousie University, he is going to attend the Ph.D. Program in
Department of Computer Science, University of Toronto beginning in Fall
2001. He can be reached by e-mail: {\tt yuana@cs.dal.ca} or by phone: {\tt
(902) 431 7933}.
\vspace{4mm}
\noindent

{\em Jeannette Janssen} is Professor of 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}.  
\vspace{4mm}
\noindent

{\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}.

%*******************************************************************
%*References
%******************************************************************* 
\bibliography{refs}

\end{document}

