Network Analysis Based on the Graph Theory

Road networks and friendship among people are examples of networks. Road networks have physical entities while social networks don't have one. Nevertheless, either they have physical entities or not, essence of networks can be summarized as relationships among objects. These relationships can be represented in matrices and can be handled by computers. The field in mathematics for studying the nature of networks is called the graph theory. Techniquies of network analysis are applied in many field including car navigation systems and facility management systems. The following is the basic procedures for operating network data represented as matrices.

Hypothetical railway network	Matrix representing a network

In the above example, each entry of the matrix has a binary value (0 or 1) depending on the existence of a linkage between the pair of points. This type of a matrix is called a connectivity matrix.

(1) Multiplication of two matrices

C++ source code ... mm.txt

Usage ... Type as follows in the Windows command prompt.

C:\>mm c01.txt c01.txt

"c01.txt" is an example of text files describing connectivity matrices. The first line includes the number of rows and columns of the matrix and the following lines include the elements of the matrix. The output will be displayed on the screen. To make further processing, please redirect the output into a file as follows.

C:\>mm c01.txt c01.txt > c02.txt

You can multiply the matrix three times or more by processing the output as follows.

C:\>mm c02.txt c01.txt > c03.txt

(2) Shimbel distance ... Topological distances of the all nodal pairs

C++ source code ... shimbel.txt

Usage ... Type as follows in the Windows command prompt.

C:\>shimbel c01.txt

The matrix representing the Shimbel distances will be put on the screen.

Valued Graph

In the above example, presence or absence of a linkage between a pair of points was taken into consideration. However we can also consider the properties of each linkage such as distance or cost. A network (or a graph) which has values indicating properties of the linkages is called a valued graph. The following programs are to calculate distance between a pair of points via a path made up of multiple linkages. Because value of infinity cannot be represented on a computer, unlike the chart below, absence of a linkage between a pair of points is expressed as ‘a sufficiently large number.’

Network including the information of distances	Matrix representing a network with distance data

(3) Processing of valued graphs (matrices of linkages given as distances) to calculate indirect connectivities

C++ source code ... vm.txt

Usage ... Type as follows in the Windows command prompt.

C:\>vm vg01.txt vg01.txt

"vg01.txt" is an example of text files describing valued graph matrices. The first line includes the number of rows and columns of the matrix and the following lines include the elements of the matrix i.e. the length of the linkage between two nodes. The infinity is represented as "9999". The output will be displayed on the screen. To make further processing, please redirect the output into a file as follows.

C:\>vm vg01.txt vg01.txt > vg02.txt

You can process the matrix further to get distances of paths of three or more steps. Please type as follows.

C:\>vm vg02.txt vg01.txt > vg03.txt

(4) Processing of valued graphs to calculate shortest path distances.

C++ source code ... dist.txt

Usage ... Type as follows in the Windows command prompt.

C:\>dist vg01.txt

The matrix representing the shortest path distances will be put on the screen.

[Reference]

• Taafe, E. J., H. L. Gauthier and M. E. O'Kelly (1996) Geography of Transportation, Second Edition, Prentice Hall, pp. 249-286.