## … at least enough to get us started!

A *network* or *graph* is a set of items, which we call *vertices*, with connections between them, called *edges*. You may also see a vertex being called a *site* (physics), a *node* (computer science), or an *actor* (sociology). An edge may also called a *bond* (physics), a *link* (computer science), or a *tie* (sociology).

Studies of networks in the social sciences typically address issues of *centrality* (who is best connected to others or has the most influence) and *connectivity* (how individuals are linked to one another through the network).

A set of vertices joined by edges is the simplest type of network – there are many ways in which networks may be more complex. For instance, there may be more than one *type* of vertex in a network, or more than one type of edge.

In a social network of people, the vertices may represent men or women; graphs composed of two types of nodes, with edges running only between unlike types, are sometimes called *bigraphs*. So-called *affiliation networks*, in which people are joined together by common membership of groups take this form, the two types of vertices representing people and groups.

Edges may carry *weights*, representing (say) how well two people like each other; they may also be *directed*, pointing from one node to another. Directed edges are sometimes called *arcs*. Graphs composed of directed edges are sometimes called *digraphs*. Digraphs can be either *cyclic* – meaning they contain closed loops of edges – or *acyclic* – meaning they do not.

(a) undirected network, single type of vertex & single type of edge; (b) network with different types of vertices and edges; (c) network with weighted vertices and edges; (d) directed network- from MEJ Newman (2003), *The structure and function of complex networks*.

One can also have *hyperedges* – edges that join more than two vertices together. Graphs containing such edges are called *hypergraphs*. Hyperedges (say) may be used to represent family ties in a social network – *n* individuals connected to each other by virtue of belonging to the same immediate family could be represented by an *n*-edge joining them.

Graphs may also evolve over time, with vertices or edges appearing or disappearing, or values defined on those vertices or edges changing.

A few other basic terms:

*Degree*: The number of edges connected to a vertex. Note that the degree is not necessarily equal to the number of vertices adjacent to a vertex, since there may be more than one edge between any two vertices. A digraph has both an *in-degree* and an *out-degree* for each vertex, which are the number of in-coming and out-going edges respectively.

*Component*: The component to which a vertex belongs is that set of vertices that can be reached from it by paths running along edges of the graphs. A digraph has both an *in-component* and an *out-component*, which are the sets of vertices from which the vertex can be reached and which can be reached from it, respectively.

*Geodesic path*: The shortest path through the network from one vertex to another. Note there may be and often is more than one geodesic path between two vertices.

*Diameter*: The diameter of a network is the length (in number of edges) of the *longest* geodesic path between any two vertices.

To be continued …