Analyzing Dynamic Hypergraphs with Parallel Aggregated Ordered Hypergraph Visualization
Paola Valdivia, Paolo Buono, Nicole Dufournaud, Catherine Plaisant, Jean-Daniel FeketeParallel Aggregated Ordered Hypergraph (PAOH see https://www.aviz.fr/paohvis) is a technique to visualize networks modeled as dynamic hypergraphs. Networks with relations that involve several entities can be more accurately represented as hypergraphs, rather than with regular graphs. In a dynamic hypergraph, the relations between entities change over time. Our visualization, PAOH, represents nodes as parallel horizontal bars, optionally colored to represent an attribute of the node. Nodes labels are placed on the left side of the display. Hyperedges are parallel vertical lines connecting the nodes, with the connections emphasized with a dot. PAOH represents time flowing from left to right as a series of time slots separated by small white gaps. Each time slot corresponds to an interval of time.
Let's see the case of a historian studying a collection of contracts describing trade relations in the 17th century in Nantes, France. She was interested in analyzing the role of a non-married merchant woman, Marie Boucher. Our collaborator wanted to understand the changing relationships that Boucher had with other merchants over time. This case study is representative of a large category of studies in social history in which people are connected through dated documents where they are mentioned, such as contracts, but also marriage certificates, and justice decisions. The Boucher dataset is composed of 59 contracts mentioning 90 persons overall. Each person is modeled as a node, and the color of the background is used to represent their family. Each contract is modeled as a hyperedge linking several persons. Each contract has a signature date. Modeling the same data as a standard graph, these 59 hyperedges would become 488 edges.
Our collaborator had already analyzed the dataset using two separate representations designed for regular graphs: node-link diagrams and TimeArcs. She found the PAOH representation clear and commented that the same analysis, using PAOH, required only one visualization and could be done more accurately. Some new findings were identified. For example, in 1667 Marie Boucher had two contracts with Jean Boucher and two others with Seigneur de Nays — from the graph representations she had assumed that two persons connected during the same year appeared in only one contract. Our collaborator also explained that three main phases had been identified after the lengthy prior analysis: an initial phase from 1660 to 1664 with mostly French trading, a second phase with cross Atlantic trade from 1666 to 1668, and a third expansion phase until 1675, after which Marie disappears from the records until a 1689 document mention of her being deceased. She stated that those phases were apparent in the PAOH visualization that represents time and connections simultaneously. She commented that it provided good narrative support, and would be useful to communicate the findings. Also, the color-coding was found useful to represent the strong —and changing— family connections.
We believe that PAOH is the first technique to provide a highly readable representation of dynamic hypergraphs. It is easy to learn and well suited for medium size dynamic hypergraphs (50-500 nodes).