Glossary of graph theory and network terms

TermDescriptionExample in citation network
GraphMathematical construct consisting of vertices or nodes, and edges that connect pairs of vertices. If the edges are directed, the graph is called a directed graph. A directed graph is acyclic when one cannot return to the same vertex following any combination of directed edges.A citation network graph is a simple directed acyclic graph.
SubgraphA part of a graph that includes a subset of the vertices and all the edges between them.
Vertex or nodeThe fundamental unit of a graph.In a citation network vertices represent papers
Arc or directed edgeA connection between a pair of nodes. It is directed when the order in which the nodes are connected is important.Arcs go from cited papers (A) to citing papers (B) to denote that some information is flowing from the former to the latter: A→B
PathA sequence of vertices such that from each vertex there is an edge to the next vertex in the sequence, as if one were visiting vertices by walking a long the edges. In a directed path, the direction of the edges matters, one would be allowed to walk only in the direction of the arcs.
Indegree, outdegree, hub and authority scoresThese are measures of the centrality (“importance”) of a paper in a citation network.
Indegree is the number of incoming arcs (number of papers cited).
Outdegree is the number of outgoing arcs (citations received).
Hub and authority scores, is the relative importance of a vertex in a network. A vertex has higher hub or authority score if it has a higher indegree or outdegree respectively, and if it is connected to other vertices with high hub or authority scores respectively.
The distribution of these measures can characterize the connectivity of the citation network, and potentially the amount of information that flows through citations.
These measures may identify “key” papers in the corpus of citations.
Temporal consistencyA citation graph is temporally consistent when the cited articles have been published earlier than the corresponding citing articles.A temporally consistent graph must be acyclic.*
*

In theory two articles can cite each other. This can happen e.g., in articles appearing in the issue. Such an instance would render the graph non-acyclic (for two papers A and B that cite each other, there is a directed cyclic path: ABA).

In theory two articles can cite each other. This can happen e.g., in articles appearing in the issue. Such an instance would render the graph non-acyclic (for two papers A and B that cite each other, there is a directed cyclic path: ABA).

From: Appendix B, Details on the Construction of Citation Graphs

Cover of Concordance Between the Findings of Epidemiological Studies and Randomized Trials in Nutrition: An Empirical Evaluation and Citation Analysis
Concordance Between the Findings of Epidemiological Studies and Randomized Trials in Nutrition: An Empirical Evaluation and Citation Analysis: Nutritional Research Series, Vol. 6 [Internet].
Technical Reviews, No. 17.6.
Moorthy D, Chung M, Lee J, et al.

NCBI Bookshelf. A service of the National Library of Medicine, National Institutes of Health.