[graph-tool] strength and clustering coefficient on weighted digraph

Alexandre Hannud Abdo abdo at member.fsf.org
Sat Mar 2 04:13:16 CET 2013


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




More information about the graph-tool mailing list