Nodes and Edges


Worksheet (docx)

Basic Terminology

A network or graph is a set of entities (aka vertices or nodes) and the connections (aka edges, links, or ties) among them. There may be an edge between every pair of nodes, no edges at all, or anything in between.


Fig. 1. Networks come in different shapes and sizes.

Only the patterns of connections is important. The way that the vertices of a network are arranged in a visualization is called a layout. Sometimes network software will layout vertices in a manner that represents quantitative properties of the network, but in the most generic case, we are free to arrange vertices in different ways as long as the pattern of connections is maintained.

Fig. 2. Three layouts of the same network.

If there is more than one edge between two vertices we call it a multi-edge. If an edge connects a vertex to itself it is called a self-edge. A network with no multi-edges and no self-edges is called a simple network.


Fig. 3. A self-edge (left) and a multi-edge (right).

If a network can be drawn on a flat piece of paper without any edges crossing it is called a planar network. It is sometimes necessary to "untangle" the nodes and edges to see that a network is planar. Most social and natural networks are NOT planar. A common example of a network that IS planar is an organization chart in a bureaucracy.

Fig. 4. Caption.


Fig. 5. Caption.

If there is an edge between two nodes, A and B, we say there is a path from A to B. If there is a path from A to B and a path to another node C, then we say there is a path from A to C.

Fig. 6. A path from vertex K through H and R to Q.

If there is a path between any two randomly selected nodes in a network then we say the network is connected and is said to have a single component. A component is a maximal subset of connected vertices. The network in Figure 6 is connected. The network in Figure 7 has 3 components.


Fig. 7. A disconnected network with 15 vertices, 20 edges, and 3 components.

Edges can be directed or not. A directed edge from A to B indicates that there is a path from A to B but not a path from B to A. The "relationship" represented by the edge is asymmetric — A being related to B does not guarantee that B is related to A. If A is the parent of B, for example, B is necessarily NOT the parent of A. Other examples would be "likes," which may be symmetric but need not be, or "is the subordinate of," which, in a well functioning bureaucracy would be asymmetric: one cannot be one's boss's boss. Figure 8 shows a directed network of kinship.


Fig. 8.  A directed network. The edges represent the relationship "is the parent of."


Q25. Use NodeXL to reproduce the organizational chart below. Take note of the appearance of the network with various layout options. Try changing the type to "directed" in the chart panel of the NodeXL ribbon. What do you say about organizational charts as networks from examining the different layouts?

President VP1
President VP2
VP1 Mgr1
VP1 Mgr2
VP2 Staff1
Mgr2 Staff2
Mgr2 Staff3
Mgr2 Staff4

Q26. Amir likes Bashir. Chastity is liked by Danica. Chastity likes Ellen. Amir likes Danica and Ellen. Franke likes everyone. Gillian likes Danica. Ellen likes Bashir. Sketch this directed network.

Q27. Consider the imaginary bibliographies shown below for 7 classic works of sociology.

  • Aron, Raymond. 1967. Les Étapes de la pensée sociologique
  • Bourdieu, Pierre. 1972. Esquisse d'une théorie de la pratique, précédé de trois études d'ethnologie kabyle (Outline of a Theory of Practice)
  • Crozier, Michel. 1964. The Bureaucratic Phenomenon
  • Durkheim, Emile. 1912. Elementary Forms of the Religious Life
  • Erikson, Kai. 1967. Wayward Puritans
  • Frazier, E. Franklin. 1955. Bourgeoisie noire
  • Geiger, Theodore. 1963. Demokratie ohne Dogma: Die Gesellschaft zwischen Pathos und Niichternheit.
Aron 1967


Bourdieu 1972


Crozier 1964


Durkheim 1912 Erikson 1967


Frazier 1955


Geiger 1963


(a) Sketch the directed network of citations.

(b) For each pair of authors count up how many times they cite the same other author.

(c) Next, for each pair of authors, count how many books cite both of them. For example, Crozier and Durkheim are cited by Aron, Bourdieu, and Erikson so the count would be 3.

Q28. Consider the three networks in the figure below. For each one, calculate the ratio of actual number of edges to the most maximum number of edges possible (assuming the graphs are simple).


Q29. Consider the series below showing the maximum number of edges (m) possible in networks with different numbers of vertices (n). Come up with a general formula for m in terms of n (that is, for a network with n vertices, what is the maximum number of edges — assuming no self-edges and no multi-edges?).


Weighted Networks

Some Mathematical Notation

Bipartite Networks