Triggering Patterns of Topology Changes in Dynamic Graphs

To describe the dynamics taking place in networks that structurally change over time, we propose an approach to search for attributes whose value changes impact the topology of the graph. In several applications, it appears that the variations of a group of attributes are often followed by some structural changes in the graph that one may assume they generate. We formalize the triggering pattern discovery problem as a method jointly rooted in sequence mining and graph analysis. We apply our approach on three real-world dynamic graphs of different natures – a co-authoring network, an airline network, and a social bookmarking system – assessing the relevancy of the triggering pattern mining approach.

• The Digital Bibliography & Library Project covers an important part of the computer science bibliography. All references published between 1990 and 2010 by 2,723 authors (recording more than 10 publications) are elected among 43 conferences/journals. Two additional attributes, named conferences and journals, are the sums of publications in respectively conference venues and journals. We build a dynamic attributed graph where the vertices are the authors and 9 timestamps reflect 5 years half-overlapping intervals ([1990-1994],[1992-1996],…,[2006-2010]). An edge means that two authors co-published at least one paper in a period.
• The Research and Innovative Technology Administration (RITA) maintains a public database giving the U.S. air carrier traffic statistics. We derive three dynamic graphs where vertices are the airports, the vertex attributes describe traffic aspects (number of departures/arrivals, number of canceled flights, number of flights diverted at destination, the mean delay of departure/arrival and the ground waiting at time departure/arrival) and the edges represent air lines. They differ by their time scale: in RITA1, attribute values are summed over days of September 2001; in RITA2, the values are accumulated over months from September 2000 to September 2002; and in RITA3, they are aggregated over weeks between 01/08/2005 and 25/09/2005 (Katrina hurricane).
• Delicious website holds social networking, bookmarking, and tagging information. In the generated dynamic graph, edges represent mutual fan relationships. Users are described by the numbers of bookmarks they shared for different categories (art, car, student, etc.). The number of categories is too large, most of them being uniquely used: we only keep the tags used at least by 500 users over the considered time period. Timestamps are aggregated by year on a period spanning from 2006 to 2010 for the quantitative experiments.