Size agnostic Change Point Detection (CPD) framework

Inference statistic helps determine points of change in the evolution of networks; The framework does not use historic data nor imposes size restrictions, and is best suited to interaction networks, also termed temporal asynchronous human communication networks. 

Paper: Hadar Miller, Osnat Mokryn. Size Agnostic Change Point Detection Framework. March 2020, PLoS ONE 15(4), pp. 1-23, e0231035. (Link)

Changes in the structure of observed social and complex networks can indicate a significant underlying change in an organization, or reflect the response of the network to an external event. Automatic detection of change points in evolving networks is rudimentary to the research and the understanding of the effect of such events on networks. Here we present an easy-to-implement and fast framework for change point detection in evolving temporal networks. Our method is size agnostic, and does not require either prior knowledge about the network’s size and structure, nor does it require obtaining historical information or nodal identities over time. We tested it over both synthetic data derived from dynamic models and two real datasets: Enron email exchange and AskUbuntu forum. Our framework succeeds with both precision and recall and outperforms previous solutions.

The performance of our framework with the KS distance metric for all permutations of ER networks that entail change. The networks were modeled with the edge connectivity probability,p1,ER,p2,ER∈ [0.05, 0.1, 0.15, …1],p1,ER≠p2,ER. Overall, the sensitivity graph depicts 380 experiments, in which each point is the average of 2x100 random networks. The framework excels in finding the hyper-parameter change. Hence, it is very sensitive to changes in the network’s density and fails to find a change only when the changes are very small, i.e., |p1,ER−p2,ER| = 0.05, as can be seen by the low f1 value at the narrow diagonal line.