strength and clustering coefficient on weighted digraph

graph-tool
#1

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

#2

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
.~´

#3

Dear Alexandre,

This is one of the .GML files: http://ubuntuone.com/58AiS1hjG62bdNF8kocfmo

2013/3/2 Alexandre Hannud Abdo <abdo(a)member.fsf.org>:

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

#4

Hi Abdo,

#5

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

#6

I just realized you were referring to the weighted degrees, so nevermind.

Cheers,
Tiago