1

How can I construct adjacency matrix from input dataset graph file, which has the following data:

The first line of the dataset file, represents the number of nodes and edges resp. The following lines represent node1 and node2 denoting an edge existing between them For example: amazon.graph dataset file contains the following

Below is the file amazon.graph
4 6 // number of nodes and edges
0 1 // edge between node 0 and 1
1 3
2 3
1 2
0 2
0 3

This data is contained in a file named "amazon.graph". I need help with a matlab function that can read the file and build adjacency matrix from the dataset file

Nikhil Katre
  • 2,114
  • 23
  • 22

1 Answers1

3

Use sparse to build the matrix:

x = [4 6
     0 1
     1 3
     2 3
     1 2
     0 2
     0 3]; %// data

adjMatrix = sparse(x(2:end,1)+1, x(2:end,2)+1, 1, x(1,1), x(1,2));

This produces a sparse matrix. You can convert to full form if needed:

adjMatrix = full(adjMatrix);

In your example, this gives

adjMatrix =

     0     1     1     1     0     0
     0     0     1     1     0     0
     0     0     0     1     0     0
     0     0     0     0     0     0

To make the graph symmetric (undirected): 

s = max(x(1,1), x(1,2)); %// take largest dimemsion
adjMatrix = sparse(x(2:end,1)+1, x(2:end,2)+1, 1, s, s); %// now matrix is square
adjMatrix = adjMatrix | adjMatrix.'; %'// apply "or" with transpose to make symmetric
adjMatrix = full(adjMatrix); %// convert to full if needed

If you have the data in a file, you can read it into the variable x using textread. For example, if the file data.txt contains the text

4     6
0     1
1     3
2     3
1     2
0     2
0     3

just use

x = textread('data.txt');

Then you can apply the above to generate the adjMatrix from x.

Luis Mendo
  • 110,752
  • 13
  • 76
  • 147
  • Would this method work if the graph dataset file contains nodes and edges in the order of thousands ? – Nikhil Katre Oct 06 '14 at 09:01
  • Also can you please tell, how to read the data from a file to build the adj matrix – Nikhil Katre Oct 06 '14 at 09:02
  • Yes, the method is memory-efficient, so it works for any reasonable size. Thousands shouln't be a problem. As for how to read the data from a file, please see updated answer – Luis Mendo Oct 06 '14 at 09:36
  • One last q Luis, I wanted to ask that suppose if the graph is undirected and edge represented in the graph is such that 0 3 is present but 3 0 is not present. So how to handle this while creating the ad matrix. I know u answered this q but somehow it got lost. I apologize to ask this again . :) – Nikhil Katre Oct 06 '14 at 16:14
  • I answered in a comment but it wasn't correct, so I deleted it. I have edited the answer with the correct way to to that: you build a square matrix with the largest of the two dimensions, and then apply "or" with its transpose – Luis Mendo Oct 06 '14 at 16:16
  • You are great Luis, thanks a lot.... just to confirm the third line of the code is adjMatrix = adjMatrix l adjMatrix ' ; am i correct ? – Nikhil Katre Oct 06 '14 at 16:26
  • In this case `'` and `.'` give the same result. But I prefer to use `.'` for transpose. See for example [here](http://stackoverflow.com/q/25150027/2586922) – Luis Mendo Oct 06 '14 at 16:35