Editing Directed acyclic graph (section)

=== Citation graphs ===
In a [[citation graph]] the vertices are documents with a single publication date. The edges represent the citations from the bibliography of one document to other necessarily earlier documents. The classic example comes from the citations between academic papers as pointed out in the 1965 article "Networks of Scientific Papers"<ref>{{citation | last = Price | first = Derek J. de Solla | date = July 30, 1965 | doi = 10.1126/science.149.3683.510 | issue = 3683 | journal = [[Science (journal)|Science]] | pages = 510–515 | pmid = 14325149 | title = Networks of Scientific Papers | url = http://garfield.library.upenn.edu/papers/pricenetworks1965.pdf | volume = 149| bibcode = 1965Sci...149..510D }}.</ref> by [[Derek J. de Solla Price]] who went on to produce the first model of a citation network, the [[Price's model|Price model]].<ref>{{citation | last = Price | first = Derek J. de Solla | date = 1976 | doi = 10.1002/asi.4630270505 |  journal = [[Journal of the American Society for Information Science]] | pages = 292–306 | volume = 27 |title = A general theory of bibliometric and other cumulative advantage processes | issue = 5 | s2cid = 8536863 }}.</ref> In this case the [[Citation impact|citation count]] of a paper is just the in-degree of the corresponding vertex of the citation network. This is an important measure in [[citation analysis]]. [[Judgment (law)|Court judgements]] provide another example as judges support their conclusions in one case by recalling other earlier decisions made in previous cases. A final example is provided by patents which must refer to earlier [[prior art]], earlier patents which are relevant to the current patent claim. By taking the special properties of directed acyclic graphs into account, one can analyse citation networks with techniques not available when analysing the general graphs considered in many studies using [[Network Science|network analysis]]. For instance [[#Transitive closure and transitive reduction|transitive reduction]] gives new insights into the citation distributions found in different applications highlighting clear differences in the mechanisms creating citations networks in different contexts.<ref>{{citation | last1 = Clough | first1 = James R. | last2 = Gollings | first2 = Jamie | last3 = Loach | first3 = Tamar V. | last4 = Evans | first4 = Tim S. | doi = 10.1093/comnet/cnu039 | issue = 2 | journal = Journal of Complex Networks | pages = 189–203 | title = Transitive reduction of citation networks | volume = 3| arxiv = 1310.8224 | year = 2015 | s2cid = 10228152 }}.</ref> Another technique is [[main path analysis]], which traces the citation links and suggests the most significant citation chains in a given [[citation graph]].

The [[Price's model|Price model]] is too simple to be a realistic model of a [[citation graph|citation network]] but it is simple enough to allow for analytic solutions for some of its properties. Many of these can be found by using results derived from the undirected version of the [[Price's model|Price model]], the [[Barabási–Albert model]]. However, since [[Price's model]] gives a directed acyclic graph, it is a useful model when looking for analytic calculations of properties unique to directed acyclic graphs. For instance,
the length of the longest path, from the n-th node added to the network to the first node in the network, scales as<ref name="ECV">{{citation | last1=Evans | first1=T.S. |last2=Calmon | first2=L. |last3=Vasiliauskaite | first3=V. | title=The Longest Path in the Price Model | journal=Scientific Reports  | volume=10 | date=2020 | issue=1 | doi=10.1038/s41598-020-67421-8 | pages=10503| pmid=32601403 | pmc=7324613 | arxiv=1903.03667 | bibcode=2020NatSR..1010503E }}</ref> <math>\ln(n)</math>.