You may know the word graph from the generic phrase "charts and graphs," but in mathematics and computer science, graph has a different definition.
In this context, a graph is a way of structuring data that emphasizes links and relationships: it consists of nodes and edges. Together, they make a kind of web. For example, you might represent a social community as a graph: the nodes might be people, and the edges, friendships between them. You could also represent trade or travel with a graph: places could be your nodes, and journeys or exchanges could be your edges.
Graphs can either be directed or undirected.
A directed graph, as the name suggests, has edges with directions. You might represent email exchanges as a directed graph, with the edge direction reflecting who's sending the email and who's receiving it.
An undirected graph has edges with no direction. A graph of social interactions at a party, for example, would probably just consist of people as nodes and interactions as edges, with no particular direction one way or the other.
There are established analytical methods for approaching network data, especially social network data. This can include identifying how relationships are distributed—are there lots of connections between all individuals? are there separate groups, perhaps tied together by a small number of individuals?—or trying to identify the relative prominence (or "centrality") of a given group or individual.
One example of a digital humanities network analysis project is Six Degrees of Francis Bacon. The project visualizes both known and statistically inferred relationships between individuals in Early Modern England.
If you're looking to perform your own network analysis, there's software that can help:
Linked Data is a concept in database creation of interoperability and interlinking—the idea that you might, for example, structure your database of archival letters in such a way that someone else might be able to easily use its data for their database of people, or vice versa.
This could mean observing "data standards," which might determine what kinds of values and fields or nodes and edges you use. (Values and fields are the key elements in relational databases—as opposed to graph databases—fields being things like "date of birth" or "country of origin" and values being things like "December 12, 1845" or "Australia.")
This might also include linking out explicitly to other sets of data—for example, you might link to an authority record like the Getty Union List of Artist Names, or to an entry in Wikidata, to verify an individual datapoint or to offer additional information—but it can also include links within the data itself.
One way of structuring data to effectively embrace Linked Data principles it to organize it as a graph. Instead of prioritizing certain kinds of data—the organizing principle of entries in a relational database, which have fields and values—you can represent each piece of data in relation to others. Instead of an art object "having" a date, for example, you would have a date node that would then link out to all the art object nodes that relate to it. LUX is an implementation of this principle for Yale's collections.