6
$\begingroup$

There has been much research related to web graphs and social graphs. They can be thought of as a kind of random graphs, but the point is that they are different from the well-known Erdős–Rényi model.

Question: Consider citations graphs in some field of research (i.e. the graphs with vertices given by publications and edges by citations). Are there any known mathematical models for them? Or are there empirical observations on the mathematical properties of such graphs (similar to those mentioned below)?

Here are some of the main properties of web graphs. I wonder about something similar for citation graphs.

  1. The diameter is quite small (~6), i.e. the Law of Six degrees of separation

  2. "Sparsity" - adjacency matrix is a sparse matrix,

  3. Power law of distribution of degrees of vertices: the number of vertices with $d$ edges scales like $C/d^{2.1}$

And there is a suggestion for the model of how web graphs are growing, namely Barabási–Albert model, with the key idea of Preferential attachment, which means that the more connected a node is, the more likely it is to receive new links. Nodes with higher degree have stronger ability to grab links added to the network. Intuitively, the preferential attachment can be understood if we think in terms of social networks connecting people. Here a link from A to B means that person A "knows" or "is acquainted with" person B. Heavily linked nodes represent well-known people with lots of relations.

See e.g. https://www.mccme.ru/free-books/dubna/raigor-4.pdf

Improve this question
$\endgroup$

1 Answer 1

Reset to default
6
$\begingroup$

A great deal is known about citation graphs. For example, an analysis of the citation graph for the computer science literature answers the three questions in the OP as:
• the connected component has a diameter of 18;
• the sparsity is characteristic of a "small world network";
• the power law degree distribution has exponent 1.71.

Concerning growth models of citation graphs, see for example A geometric graph model of citation networks with linearly growing node-increment.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you very much ! Is there any model how these graphs are formed ? Please see newly added part of the question. $\endgroup$
    – Alexander Chervov
    Commented Jun 11, 2018 at 20:06
  • $\begingroup$ added one recent growth model. $\endgroup$
    – Carlo Beenakker
    Commented Jun 11, 2018 at 20:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .