Message Boards Message Boards

Identifying & linking common vertices in 2 or more unequal multi-graphs?

I've just started teaching myself to work with graphs, and have created two, directed edge multi-graphs of letters from two sets of matched author and recipient lists. The graphs are unequal because they have different total numbers of author/recipients. Here, in a simplified form, is what I've been doing so far:

adAuthors={"mary", "peter", "peter", "peter"}
adRecipients={"jane", "arthur", "diana", "diana"}
adGraph=Graph[Thread[DirectedEdge[adAuthors, adRecipients]], VertexLabels -> Placed["Name", Tooltip]]

In other words, Mary wrote a letter to Jane, and Peter wrote letters to Arthur and (twice) to Diana. This data is a subset from a much larger dataset with many more attributes and where the authors and recipients are identified by their ID numbers. The second graph is constructed the same way. Here's an example output using my real data:

enter image description here

I know that the two graphs (though of unequal length) share several common authors and recipients, and I'd like to find their list of common vertices, and also show this in a combined graph, indicating where the two graphs are connected. Later, I'd like to repeat this procedure for several more graphs, all sharing a small number of common authors and recipients.

Could someone offer some suggestions on how best to approach this? I'm very open to importing and working with my original spreadsheet data in MMA differently and more efficiently. These were just my very first beginner's steps — many thanks.
POSTED BY: Arno Bosse
4 Replies
Sort By:

Marco and Vitaliy, thank you both very much for your patient and generous responses. I will have time tomorrow to look at them more carefully.

POSTED BY: Arno Bosse

...friendships forged in fire ;-) @Arno Bosse @Marco Thiel

POSTED BY: Vitaliy Kaurov

Some thoughts to add to Marco's... Let's get a list of many random names:

names = EntityValue[RandomEntity["GivenName", 100], "Name"]

enter image description here

Get two non-intersecting sets:

adAuthors = names[[;; 30]];
adRecipients = names[[-30 ;;]];

Create a symbol that can get 2 random potentially overlapping graphs: 

adGraph := 
  Graph[Thread[
    DirectedEdge[RandomChoice[adAuthors, 40], 
     RandomChoice[adRecipients, 40]]], VertexLabels -> "Name", 
   GraphLayout -> "BipartiteEmbedding", 
   Background -> RandomColor[Hue[_, .5]], ImageSize -> 400];

and get 2 random graphs:

adGraphSAMPLE = {adGraph, adGraph}

enter image description here

See intersections of edges and vertices:

interVert = Intersection @@ (VertexList /@ adGraphSAMPLE)
interEdges = Intersection @@ (EdgeList /@ adGraphSAMPLE)

enter image description here

Visualize in your graphs:

HighlightGraph[#, Join[interVert, interEdges],
   GraphLayout -> "BipartiteEmbedding", VertexLabels -> "Name", 
   GraphHighlightStyle -> "Thick"] & /@ adGraphSAMPLE

enter image description here
POSTED BY: Vitaliy Kaurov

HI Arno,

I am not sure whether this is what you need, but here are some pieces of code. First I create two similar graphs with some common nodes.

adAuthors = {"mary", "peter", "peter", "peter"};
adRecipients = {"jane", "arthur", "diana", "diana"};
adAuthors2 = {"paul", "victor", "mary", "diana", "peter"};
adRecipients2 = {"peter", "mary", "paul", "paul", "alonso"};

We can plot the graphs separately:

adGraph = 
 Graph[Thread[DirectedEdge[adAuthors, adRecipients]], 
  VertexLabels -> Placed["Name", Tooltip]]

and 

adGraph2 = 
 Graph[Thread[DirectedEdge[adAuthors2, adRecipients2]], 
  VertexLabels -> Placed["Name", Tooltip]]

We can user Union to generate a list of all authors and all recipients.

Union[adAuthors, adAuthors2]
(*{"diana", "mary", "paul", "peter", "victor"}*)

and 

Union[adRecipients, adRecipients2]
(*{"alonso", "arthur", "diana", "jane", "mary", "paul", "peter"}*)

We can also plot the joint graph like so:

adGraphjoin = 
 Graph[Thread[DirectedEdge[Join[adAuthors, adAuthors2], Join[adRecipients, adRecipients2]]], 
  VertexLabels -> Placed["Name", Tooltip]]

enter image description here

So a combination of Union and Join functions should do the trick for you.

Best wishes from Aberdeen and thanks again for the great conference/workshop in Oxford, Marco
POSTED BY: Marco Thiel
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Tag limit exceeded
Note: Only the first five people you tag will receive an email notification; the other tagged names will appear as links to their profiles.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract