Introduction

Real-life graphs usually have various kinds of events happening on them, e.g., product purchases in online social networks and intrusion alerts in computer networks. The occurrences of events on the same graph could be correlated, exhibiting either attraction or repulsion. Such structural correlations can reveal important relationships between different events. Unfortunately, correlation relationships on graph structures are not well studied and cannot be captured by traditional measures.

In this work, we design a novel measure for assessing two-event structural correlations on graphs. Given the occurrences of two events, we choose uniformly a sample of “reference nodes” from the vicinity of all event nodes and employ a rank correlation measure to compute the average concordance of event density changes. Significance can be efficiently assessed by the nice property of being asymptotically normal under the null hypothesis. In order to compute the measure in large scale networks, we develop a scalable framework using di?erent sampling strategies. The complexity of these strategies is analyzed. Experiments on real graph datasets with both synthetic and real events demonstrate that the proposed framework is not only effective, but also efficient and scalable.

Example

Two events occurring on the same graph could be correlated. Two illustrative examples are shown in the figure below. In Figure (a), A and B exhibit a positive correlation (attraction). In the context of a social network, they could be two baby formula brands, Similac and Enfamil. Their distributions could imply that there exist “mother communities” in the social network where different mothers would prefer different baby formula brands. The two brands attract each other because of the communities. An example of negative correlation (repulsion) could be that people in an Apple fans’ community would probably not buy products of ThinkPad and visa versa, as conveyed by Figure (b). We name this kind of structural correlation as Two-Event Structural Correlation (TESC).

For more details about the work, please refer to the documents