strength and clustering coefficient on weighted digraph
Dear Graph-toolers, thanks for this great library, I am really enjoying my first contact with it and might spread it for our research here in IFSC/USP (Brasil, we do Physics here as well :-). I am not being able to find out how to get the degrees calculated with the weights (i.e. strengths) and I need to get clustering coefficients (i.e. transitivity) for the same kind of graphs, that is, weighted digraphs. Is this possible in graph_tool? BTW: this is not possible in networkx and igraph. Gephi can do the job, but i can't automate it, even using scripting plugin. best regards and cheers, Renato -- GNU/Linux User #479299 labmacambira.sf.net
On 01-03-2013 22:51, Renato Fabbri wrote:
I am not being able to find out how to get the degrees calculated with the weights (i.e. strengths) and I need to get clustering coefficients (i.e. transitivity) for the same kind of graphs, that is, weighted digraphs.
Is this possible in graph_tool?
Ni! Hi Renato, If you have weights on a graph, you probably have vertex and edge properties encoded in your graphml file. You can find these properties with: g.list_properties() and then access, for example an edge property, with g.edge_properties["the name you found listed"] Take a look at the section "Internal property maps" in: http://projects.skewed.de/graph-tool/doc/graph_tool.html So that's how you access those weights, and from there you can perform your degree calculations however you need. If the degrees won't change during your processing, you might want to store them in a property map for efficiency, instead of recalculating them whenever you need the value. You can create a property map as as explained in the section "Creation of new property maps" of that same page. Regarding the clustering coefficient, could you specify what it is that you want to calculate? Graph-tool provides the two standard clustering measures (local and global) plus one extended measure that accounts for larger cycles. However none of those incorporate weights. See: http://projects.skewed.de/graph-tool/doc/clustering.html The reason is that there is no single or standard way to account for weights in the calculation of a clustering coefficient, not to mention there is no single way to define clustering for a directed graph. Which also explains why those other libraries don't do it as well. Clustering is a very unspecific measure, so if you have a specific application need, you must first understand why you want to calculate some kind of clustering, to then define how, and then implement the specific solution your problem calls for. So if you already have a formal description of what you need, for example an article with a mathematical/algorithmic description of the specific weighted clustering you want to calculate, you can use graph-tool to program that calculation in either python or c++ (a choice which will depend on your efficiency needs). However if you don't know exactly what you need, you must first figure that out. There is no such thing as a one-size-fits-all formula for "weighted clustering". Maybe Tiago has better pointers, but I think that covers it. Feel free to expand your question if I did not fully understand it. Cheers, ale .~´
Dear Alexandre, This is one of the .GML files: http://ubuntuone.com/58AiS1hjG62bdNF8kocfmo 2013/3/2 Alexandre Hannud Abdo <abdo@member.fsf.org>:
On 01-03-2013 22:51, Renato Fabbri wrote:
I am not being able to find out how to get the degrees calculated with the weights (i.e. strengths) and I need to get clustering coefficients (i.e. transitivity) for the same kind of graphs, that is, weighted digraphs.
Is this possible in graph_tool?
Ni! Hi Renato,
If you have weights on a graph, you probably have vertex and edge properties encoded in your graphml file.
You can find these properties with:
g.list_properties()
and then access, for example an edge property, with
g.edge_properties["the name you found listed"]
Take a look at the section "Internal property maps" in:
http://projects.skewed.de/graph-tool/doc/graph_tool.html
So that's how you access those weights, and from there you can perform your degree calculations however you need.
If the degrees won't change during your processing, you might want to store them in a property map for efficiency, instead of recalculating them whenever you need the value.
You can create a property map as as explained in the section "Creation of new property maps" of that same page.
I think I got it (even beforehand). I could not get the strength in a direct manner as I get the degree. I fell that is because I am not understanding something.
Regarding the clustering coefficient, could you specify what it is that you want to calculate?
frac of numb of closed triads.
Graph-tool provides the two standard clustering measures (local and global) plus one extended measure that accounts for larger cycles. However none of those incorporate weights. See:
http://projects.skewed.de/graph-tool/doc/clustering.html
The reason is that there is no single or standard way to account for weights in the calculation of a clustering coefficient, not to mention there is no single way to define clustering for a directed graph.
Thanks. This is valuable information which I believed so but I did not find a direct reference to.
Which also explains why those other libraries don't do it as well.
Ok. Besides that, there is a clustering coeff for digraphs is Gephi and graph tool and they differ.
Clustering is a very unspecific measure, so if you have a specific application need, you must first understand why you want to calculate some kind of clustering, to then define how, and then implement the specific solution your problem calls for.
So if you already have a formal description of what you need, for example an article with a mathematical/algorithmic description of the specific weighted clustering you want to calculate, you can use graph-tool to program that calculation in either python or c++ (a choice which will depend on your efficiency needs).
However if you don't know exactly what you need, you must first figure that out. There is no such thing as a one-size-fits-all formula for "weighted clustering".
Thanks!! Again!
Maybe Tiago has better pointers, but I think that covers it.
Feel free to expand your question if I did not fully understand it.
Cheers,
ale .~´
Cheers. Your detailed and helpful response was very appreciated. There is more info on what we are doing here: http://www.wiki.nosdigitais.teia.org.br/ARS and here: http://labmacambira.sourceforge.net/redes -- GNU/Linux User #479299 labmacambira.sf.net
On 03/05/2013 10:26 AM, Renato Fabbri wrote:
I think I got it (even beforehand). I could not get the strength in a direct manner as I get the degree. I fell that is because I am not understanding something.
Weighted degrees are not built in. But you can get it with a simple loop: k = sum(w[e] for in v.out_edges()) In this case, the tip Abdo gave regarding storing in a property map may com in handy, so you use the values again in the future: ks = g.new_vertex_property("double") for v in g.vertices(): ks[v] = sum(w[e] for in v.out_edges())
Regarding the clustering coefficient, could you specify what it is that you want to calculate?
frac of numb of closed triads.
Without considering the weights? How is this different from the traditional unweighted clustering coefficient?
Cheers. Your detailed and helpful response was very appreciated. There is more info on what we are doing here: http://www.wiki.nosdigitais.teia.org.br/ARS and here: http://labmacambira.sourceforge.net/redes
Thanks for the references, and good luck with your project! Cheers, Tiago -- Tiago de Paula Peixoto <tiago@skewed.de>
Hi Abdo, On 03/02/2013 04:13 AM, Alexandre Hannud Abdo wrote:
If the degrees won't change during your processing, you might want to store them in a property map for efficiency, instead of recalculating them whenever you need the value.
Just a small note: Getting the degrees is a constant operation, except for filtered graphs where it O(k). So unless you are using a filtered graph, there should be no efficiency difference. Cheers, Tiago -- Tiago de Paula Peixoto <tiago@skewed.de>
On 03/05/2013 08:38 PM, Tiago de Paula Peixoto wrote:
Hi Abdo,
On 03/02/2013 04:13 AM, Alexandre Hannud Abdo wrote:
If the degrees won't change during your processing, you might want to store them in a property map for efficiency, instead of recalculating them whenever you need the value.
Just a small note: Getting the degrees is a constant operation, except for filtered graphs where it O(k). So unless you are using a filtered graph, there should be no efficiency difference.
I just realized you were referring to the weighted degrees, so nevermind. Cheers, Tiago -- Tiago de Paula Peixoto <tiago@skewed.de>
participants (3)
-
Alexandre Hannud Abdo -
Renato Fabbri -
Tiago de Paula Peixoto