### Glossary of graph theory and network terms

View in own window

Term | Description | Example in citation network |
---|

Graph | Mathematical 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. |

Subgraph | A part of a graph that includes a subset of the vertices and all the edges between them. | |

Vertex or node | The fundamental unit of a graph. | In a citation network vertices represent papers |

Arc or directed edge | A 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 |

Path | A 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 scores | These 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 consistency | A 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: *A* → *B* → *A*).