The structure of the graph

Citation networks belong to a broader class of topologies called scale-free graphs, where the node degree distribution follows a power-law [9]
$P(k)=k^{-\gamma}$ in contrast with randomly generated graphs where the degree distribution has an exponential falloff [10]. Our dataset closely follows the power-low distribution (figure 1).

Figure 1: Power-low distribution of vertex degree
\begin{figure}
\begin{center}\leavevmode
\setlength{\epsfxsize}{1\hsize}
\centerline{\epsfbox{deg_histogram.eps}}
\end{center}
\end{figure}

Another property of the graph is its small diameter. We have run an approximate diameter measurement on the graph, and the maximum path length we were able to find was 10 hops. Such graphs have also been widely studied and are called the small-world graphs.

Citation networks are not the only type of structures that can be extracted from the publications data; a significant body of research deals with collaboration networks, i.e. graphs in which the nodes represent the authors and an edge exists between two nodes whenever the two authors have co-published a paper. Collaboration networks have also been shown to be scale-free small worlds. In fact, networks with these two properties are ubiquitous and include telecommunication networks, social networks, networks of chemical interactions in cells, and food chains in ecosystems. M. E. J. Newman [11] and A.L Barabasi [16] present a broad survey of the interdisciplinary field of complex networks.

The question that arises is whether the knowledge about the structural properties of citation networks can be used to design heuristics that would be better suited for this type of graphs.

Ali Salehi 2005-04-29