Science of networks

… 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).

Basic network with 8 vertices and 10 edges

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.

Four basic types of networks

(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 …