Paper Review: Event-based Framework for Characterizing the Evolutionary behavior of Interaction Graphs

Paper Review:

1. An Event-based Framework for Characterizing the Evolutionary behavior of Interaction Graphs
Asur et. al. Ohio State University, Columbus
The proposed method works on a sequence of graphs and call it the temporally varying interaction graphs. Each graph corresponds to a snapshot in time. In the DBLP example each graph represents co-authorship in a span of 1 year.
Method:
- First a graph clustering algorithm (MCL) is used to find clusters in each graph.
- Cluster operators are defined: Continue, k-Merge, k-Split, Form, Dissolve
- Individual node operators defined: Appear, Disappear, Join, Leave
- Bit matrix operations on adjacency matrix is designed to identify occurrence of each of the events between consecutive pairs of graphs (Note each operation defines a type of event)
- Define indices based on counts of each of the events: Stability index, Sociability index, Popularity Index, Influence Index

Comments:
- There is no weight on the connecting edges between nodes. How can we use changing connection strengths?
- In the DBLP example, if 3 authors co-author a paper, how is it different from pairs co-authoring 2 different papers (with a common author)

The big problem: From Itemsets/Episodes to Graphs
1. How do we use frequent itemsets/episodes of sizes > 2, to build graphs (which only have pair wise information)?
2. Is graph the only way to characterize a network? Doesn't it ignore higher order interactions (presence/absence of long episodes or large itemsets)