Nodes and Edges

Files

Worksheet (docx)
Powerpoint

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."

---

---

Exercises

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

+ Show solution

Enter the information from the table above on the edges worksheet.
On the vertices worksheet, copy the vertex names in the first column to the Label column.
Press the Refresh Graph button. The result will almost certainly NOT look like an organizational chart. We'll fix that momentarily.

On the vertices worksheet, select the cell range containing the vertices and adjust their appearance using the buttons on the NodeXL ribbon.
(if you have trouble seeing your vertices and/or labels try setting vertex size to 3.5 and pushing zoom all the way to the left and scale all the way to the right)
Click on the select cursor in the graph window

Drag the vertices one by one until they look something like this:

One layout you might have seen is shown below. The topology (what is connected to what) is the same as above but this layout makes it appear that VP1 is at the middle of the organization — the four people on either side have to go through her and this might make her some sort of "gatekeeper."

But we've left something out. The vertical dimension in a "normal" organizational chart implies a relationship of "gives orders to" or "takes orders from" or "is the supervisor of" or "is the subordinate of." Each of these is an asymmetric relationship and the network (graph) they produce is a directed one (also known as a directed graph or digraph). In NodeXL we can switch the type of the graph in the graph panel of the NodeXL ribbon. To make the lines and arrows easier to see we go to the edges worksheet and then use the edgewidth button in the visual properties panel.

Download the NodeXL file here.

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.

+ Show solution

solution

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 Crozier Durkheim Frazier Geiger

Bourdieu 1972 Aron Crozier Durkheim Frazier Geiger

Crozier 1964 Durkheim Geiger

Durkheim 1912

Erikson 1967 Aron Durkheim Frazier Geiger

Frazier 1955 Durkheim

Geiger 1963 Durkheim Frazier

(a) Sketch the directed network of citations.

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

+ Click to show sample data table

Author 1	Author 2	Shared Bibliographic Entries
Aron	Bourdieu
Aron	Crozier
Aron	Durkheim
Aron	Erikson
Aron	Frazier
Aron	Geiger
Bourdieu	Crozier
Bourdieu	Durkheim
Bourdieu	Erikson
Bourdieu	Frazier
Bourdieu	Geiger
Crozier	Durkheim
Crozier	Erikson
Crozier	Frazier
Crozier	Geiger
Durkheim	Erikson
Durkheim	Frazier
Durkheim	Geiger
Erikson	Frazier
Erikson	Geiger
Frazier	Geiger

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

+ Click to show sample data table

Author 1	Author 2	Times Cited Together
Aron	Bourdieu
Aron	Crozier
Aron	Durkheim
Aron	Erikson
Aron	Frazier
Aron	Geiger
Bourdieu	Crozier
Bourdieu	Durkheim
Bourdieu	Erikson
Bourdieu	Frazier
Bourdieu	Geiger
Crozier	Durkheim
Crozier	Erikson
Crozier	Frazier
Crozier	Geiger
Durkheim	Erikson
Durkheim	Frazier
Durkheim	Geiger
Erikson	Frazier
Erikson	Geiger
Frazier	Geiger

+ Show solution

Author 1	Author 2	Shared Bibliographic Entries
Aron	Bourdieu	4
Aron	Crozier	2
Aron	Durkheim	0
Aron	Erikson	3
Aron	Frazier	1
Aron	Geiger	2
Bourdieu	Crozier	2
Bourdieu	Durkheim	0
Bourdieu	Erikson	4
Bourdieu	Frazier	1
Bourdieu	Geiger	2
Crozier	Durkheim	0
Crozier	Erikson	2
Crozier	Frazier	1
Crozier	Geiger	1
Durkheim	Erikson	0
Durkheim	Frazier	0
Durkheim	Geiger	0
Erikson	Frazier	1
Erikson	Geiger	2
Frazier	Geiger	1

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.

Author 1	Author 2	Times Cited Together
Aron	Bourdieu	0
Aron	Crozier	1
Aron	Durkheim	2
Aron	Erikson	0
Aron	Frazier	2
Aron	Geiger	2
Bourdieu	Crozier	0
Bourdieu	Durkheim	0
Bourdieu	Erikson	0
Bourdieu	Frazier	0
Bourdieu	Geiger	0
Crozier	Durkheim	2
Crozier	Erikson	0
Crozier	Frazier	2
Crozier	Geiger	2
Durkheim	Erikson	0
Durkheim	Frazier	4
Durkheim	Geiger	4
Erikson	Frazier	0
Erikson	Geiger	0
Frazier	Geiger	3

Download NodeXL files: citations, bibliographic, cocitation.

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

+ Show solution

No edges can be added to the network on the left. It currently has 10 edges and so the ratio is $\frac {10} {10} = 1.0$. The middle network has 5 edges out of a possible 10; the ratio is $\frac {5} {10} = 0.5$. The network on the right has zero edges so the ratio is 0.0.

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

+ Show solution

Each time we add a vertex, we can add an edge from all the existing vertices, that is, we add (n-1) new edges. And the number added last time was (n-2) and before that (n-3) all the way down to when we added 1 edge going from 1 vertext to 2.
text}

(1)

\begin{equation} m (n) = 1 + 2 + 3 + ... + (n-2) + (n-1) \end{equation}

Using the method supposedly invented by a young Gauss, we can take two copies of 1+2+…+(n-1), reverse one of them and then add up the corresponding elements in each to get

	1	+	2	+	…	+	(n-1)
	(n-1)	+	(n-2)	+	…	+	1
	n	+	n	+	…	+	n	=	(n-1) * n

so the number we want is

(2)

\begin{align} m (n) = \frac {(n-1) \times n} {2} \end{align}

---

---

Weighted Networks

Some Mathematical Notation

Bipartite Networks