I have a directed graph, S, where each vertex stores several integers of attributes. I think it might be called a "attribute relational graph" or just an old fashioned "attributed graph". The networkx Python package allows any attributes to be added to each vertex, but I can't figure out how to pair these attributes with features of the graph.

Let's say I have the following vertices representing moments in time:

  • S1, where Alice has \$1, Bob has \$2, and Cindy has \$5.
  • S2, where Alice has \$0, Bob has \$3, and Cindy has \$5.
  • S3, where Alice has \$0, Bob has \$0, and Cindy has \$8.

Edges between the vertices imply a temporal connection between the moments in time, for example, before and after a transaction between Alice, Bob, and Cindy. Additionally, vertex weight and edge weight are the frequency of that state or transaction occurring over a long period of sampling at discrete time intervals.

My question is, how can I compute correlations between those numeric attributes and the graph topology?

The only place I can think to start would be to cluster S, using the graph topology, and analyze the change of attributes between vertices within each cluster. For that you could define a similarity metric like the difference between the edge connecting each pair of vertices and check if this is correlated within a cluster.

Are there any standard algorithms for this type of analysis or am I looking at all custom code?

Other things I'd also be interested in computing,

  • A greedy "loss-only" path for Alice, what is the shortest number of transactions to make her broke from any given point.
  • The number of occurrences in the graph where Bob acts an an intermediate party to Alice and Cindy.
  • 1
    $\begingroup$ I believe this is a topic being addressed in current research $\endgroup$ – cing Aug 30 '12 at 0:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.