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

Question: consider citatations graphs in some field of research are there any known mathematical models for them ? Emperical observations on mathematical properties of such graphs (similar to mentioned below) ?

Definition: Citation graphs are graphs with vertices given by publications and edges by citations.

Here are main properties of webgraphs, I wonder about something similar for citation graphs.

1) Diameter is quite small (~6) or Law of Six degrees of separation

2) "Sparsity" - adjacency matrix is sparse matrix,

3) Power law of distribution of degrees of vertices: C/d^(2.1) - number of vertices with "d" edges

And there is suggestion for the model how webgraphs are growing: Barabási–Albert model, with the key idea of Preferential attachment:

Preferential attachment 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


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.

| cite | improve this answer | |
  • $\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 Jun 11 '18 at 20:06
  • $\begingroup$ added one recent growth model. $\endgroup$ – Carlo Beenakker Jun 11 '18 at 20:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.