igraph-help
[Top][All Lists]

## Re: [igraph] Help required - How to perform matrix multiplication in igr

 From: Pranay Vasani Subject: Re: [igraph] Help required - How to perform matrix multiplication in igraph-python Date: Wed, 13 Jan 2016 08:47:23 +0530

Thanks Tamas.
Here is my reply inline >>.

Hello,

> I have a bipartite graph and i want to compute the square of the adjacency
> matrix.
> How to do it in igraph-python?
You don't ;) igraph-python is not designed for matrix operations. Your
best bet is to use a sparse matrix class from SciPy (Scientific
Python). NumPy probably won't be enough because NumPy matrices are
dense and they will be too slow for an IMDb data set (assuming that it
contains tens or hundreds of thousands of nodes). So, basically, you
take the edge list of the graph, convert it into a SciPy sparse matrix
(look for scipy.sparse.coo_matrix), and then perform the
multiplication using SciPy.
>> You are right, I have number of nodes running into thousands and matrix [actor-movie] is going to be sparse. I will explore the Scipy sparse matrix multiplication.

> I am analyzing IMDb data set where i have information about actor and movie.
> I want to find out which actors acted in a movie and which movies have
> common actors.
You don't need matrix multiplication for that. Just get the adjacency
list of the graph, convert each item in the adjacency list to a set,
and then perform set intersections:

neis = [set(x) for x in g.get_adjlist()]

Then neis[i].intersection(neis[j]) will give you the common neighbors
of nodes i and j.

You can also use bipartite_projection() - what's wrong with that?

>> The issue here is i have actors and movies as nodes and edge represents actor acting in a given movie. Adjaceny matrix has 1 where actor has acted in a movie else 0. Squaring the adjacency matrix will produce a count of greater than 1 which i can further use as weights to depict the co-starring of actors or movies that have # of actors in common.
bipartite_projection() also produced a matrix with values 0 and 1. May be i am missing something here. If bipartite projection produces a matrix with values greater than 1 where-ever applicable it will solve the problem.
E.g there are 3 actors and 2 movies and adjacency is as below
a1 - m1
a2 - m1
a3 - m2
a1 - m2
a2 - m2

adjacency matrix for pair a1-a2 should have 2 as both of them have acted in 2 movies together and m1-m2 should also have value of 2 as both the movies have 2 actors in common

Thanks
Pranay

On Wed, Jan 13, 2016 at 2:37 AM, Tamas Nepusz wrote:
Hello,

> I have a bipartite graph and i want to compute the square of the adjacency
> matrix.
> How to do it in igraph-python?
You don't ;) igraph-python is not designed for matrix operations. Your
best bet is to use a sparse matrix class from SciPy (Scientific
Python). NumPy probably won't be enough because NumPy matrices are
dense and they will be too slow for an IMDb data set (assuming that it
contains tens or hundreds of thousands of nodes). So, basically, you
take the edge list of the graph, convert it into a SciPy sparse matrix
(look for scipy.sparse.coo_matrix), and then perform the
multiplication using SciPy.

> I am analyzing IMDb data set where i have information about actor and movie.
> I want to find out which actors acted in a movie and which movies have
> common actors.
You don't need matrix multiplication for that. Just get the adjacency
list of the graph, convert each item in the adjacency list to a set,
and then perform set intersections:

neis = [set(x) for x in g.get_adjlist()]

Then neis[i].intersection(neis[j]) will give you the common neighbors
of nodes i and j.

You can also use bipartite_projection() - what's wrong with that?

T.

_______________________________________________
igraph-help mailing list