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.

sampleNetworks01.gif

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.

sampleNetworks03.gif

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.
sampleNetworks02.gif

Fig. 4. Caption.

orgchart01.gif

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.
sampleNetworks04.gif

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.

sampleNetworks05.gif

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.

ch01-0008.gif

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?

orgchart01.gif
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

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.

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

sampleNetworks01.gif

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

ch01-q0028-01.gif


Weighted Networks

Some Mathematical Notation

Bipartite Networks