Main path analysis /citation network algorithms in Igraph

Usage
, , ,
1

Hi everyone,

I was wondering if anyone has experience with / implemented main path analysis using Igraph in R. Pajek has a very efficient implementation but i would like to analyse many different graphs, which is why it would be much more comfortable to do the analysis directly in R, as well.

Best
Jakob

1 Like
2

If you could provide a concise (but complete) summary of what “main path analysis” is, someone might answer even if they were not familiar with the concept before.

3

Basically, the idea is to identify the ‘most important’ path (or a set thereof) in a citation network (i.e. a DAG).

The method proceeds in two steps:

  1. Compute an edge weight (e.g. Search Path Count [SPC] counts the number of paths from source nodes to sink nodes that go through an edge)

  2. Select edges constituting the main path (e.g. starting from source nodes iteratively select the edge with the highest weight or select the path with the overall highest weight)

As you can see, the principle is very simple. I could imagine that igraph already has the features implemented ‘under the hood’ for use in related methods, but dealing with igraph’s internals is above my programming skill level.

1 Like
4

In principle, the idea could be implemented without too much problems. The difficulty however is that there are quite some variants of “main path analysis”, which we probably don’t all want to implement. Nevertheless, it could be something that might be of interest to igraph users.

My co-authors and I have actually been working on an alternative approach to “main path analysis”, which we call “intermediacy”, which we believe provides better results than “main path analysis”. I was thinking of implementing this in igraph at one point. It would then be reasonable to also implement (one variant of) “main path analysis”. It might take some time before I will get around to this. So, if there is anybody else that already wants to implement “main path analysis”, that would be great. I’d be more than happy to assist with reviewing any contribution.

1 Like
5

Hello guys,

Did you implemented the Main path analysis?

Thanks In advance :wink:

6

No, it has not been implemented. Are you feeling up for it? Contributions are always welcome.

1 Like
7

I implemented some main path analysis methods in a Julia package, in case you’re interested. No guarantees, though :smiley: Sadly, I don’t know any C or I’d be happy to contribute.

1 Like
8

@Jakob Did you implemented the SPLC? That is really nice to know :smiley:

9

I gonna try to devise it in Python :smiley:

10

@szhorvat However, I dont know exactly where to start … :S