Dynamic graph is a graph whose edges and nodes may appear and disappear over time. Examples are phone call graphs, webpage visiting graphs and email graphs. We believe that dynamic graphs can be analyzed to find information on communities and patterns, but their dynamic character makes it difficult to extract such information in a static manner. So the evolution of the dynamic graphs over a period must be integrated or averaged. A key problem is how to decide the length of the period.
Identifying communities is related to the graph clustering problem which, even for static graphs, is a hard problem. Another challenging task is to detect the connecting patterns of the nodes. Depending on the roles of the nodes, these patterns may change gradually or suddenly over the time. We need to quantify and classify them for further investigation. Scan statistics is a powerful tool to detect communication volume changes in dynamic graphs. But it lacks the facility to detect localized communication patterns and how they change over time. We propose varieties of scan statistics for such purposes.
The dynamic graph we are working with is an email communication network. It covers the email exchanges for more than 10,000 people over one year. It includes different types of email addresses, both personal addresses and mailing lists. There are also communities embedded in it.