Descriptions of networks

The graph in the left upper panel of Figure 2.2 repeats the graph in Figure 2.1. The left lower panel gives its formal mathematical description. The right side of this figure has the transcription of the graph description into Pajek's input format. It has descriptions of the sets of vertices, arcs, and edges. Describing the set of vertices starts with the keyword * Vert ices followed by the number of vertices, n. The following (text) lines contain the vertex number (index) followed by the vertex label. The vertex numbers are consecutive integers from 1 to n. The description of the set of arcs starts with the keyword *Arcs. The following lines, one for each arc, have pairs of integers: the first is the index of an arc's initial vertex, the second is the arc's terminal vertex index. Similarly, the description of the set of edges starts with the keyword * Edges. In each of the following lines, with each edge on a separate line, there is a pair of integers: the indices of its end-vertices. The descriptions of lines can also contain a third number (integer or real) representing the weight of the line. All Pajek files have the extension 'net', e.g. example . net.

Graph descriptions: a picture, its mathematical statement, and Pajek

Figure 2.2 Graph descriptions: a picture, its mathematical statement, and Pajek's input file.

Degree distributions for the graph in Figure 2.2.

Figure 2.3 Degree distributions for the graph in Figure 2.2.


Examples of numerical properties of vertices are degree measures. The degree of vertex v, deg(u), counts the number of lines with v as an end-vertex. The indegree of vertex v, indeg(u), counts the number of lines with v as a terminal vertex. The outdegree of vertex v, outdeg(u), counts the number of lines with v as an initial vertex. Three degree tables for our example graph from Figure 2.2 are presented on the left of Figure 2.3. On the right is a Pajek file listing indegrees.

Other types of degrees can be defined when needed. For example, restricting the indegree to arcs, indeg^Cu), counts the number of arcs with v as a terminal vertex.

Since each initial vertex is counted once on each arc and twice on each edge,

and similarly

where 80 is the set of undirected loops.

In a graph Q = (V, £), a vertex v is called an initial vertex of Q iff4 indeg(u) = 0. It is a terminal vertex of Q iff outdeg(u) = 0.

Descriptions of properties

Vertex properties are represented in Pajek with one of three data objects depending on their measurement scales. Numerical properties are represented with vectors, ordinal or nominal properties by partitions and linear orderings by permutations. A label can also be attached to each vertex in the network description file.

For this network, n = 12, m = 23, indeg(e) = 3, outdeg(e) = 5, and deg(e) = 6. 4 We use the standard convention of using 'iff' for 'if and only if. '

All three data objects have the same Pajek file structure: *vertices n

A VECtor file has numeric data for all vertices where DiGl: the property has value vt on vertex i;

A CLUstering file has a partition of vertices representing nominal or ordinal data about vertices where

vt gN: vertex i belongs to the cluster vt;

A PERmutation file has an ordering of vertices where vt gN: vertex i is at the vrth position.

Vector files have the extension 'vec' (e.g. example . vec), clustering files have the extension 'clu' (e.g. example. clu), and permutation files have the extension 'per' (e.g. example .per). The Pajek file on the right of Figure 2.3 is a vector file. It could also be a clustering file if the analyst wanted to cluster vertices according to their degrees.

Visualizations of properties

Any numerical property can be displayed in a picture of a network. A vertex can be shown by its size (width and height) and by its coordinates (x, y, z). A nominal property can be shown as a color or a shape or by its label (content, size, and color).

We can assign numerical values to links in Pajek. A link can be displayed as a value, its thickness, or by a gray level. Nominal vales can be assigned as a label, a color (and also as a line pattern,[1] e.g. solid, dotted, straight, etc.).

  • [1] See the Pajek manual (Batagelj and Mrvar 1996-2013), Section 5.3.
< Prev   CONTENTS   Next >