Extracting real-time insights from graphs and social streams

Abstract

Many streaming applications in social networks, communication networks, and information networks are built on top of large graphs Such large networks contain continuously occurring processes, which lead to streams of edge interactions and posts. For example, the messages sent by participants on Facebook to one another can be viewed as content-rich interactions along edges. Such edge-centric streams are referred to as graph streams or social streams. The aggregate volume of these interactions can scale up super-linearly with the number of nodes in the network, which makes the problem more pressing for rapidly growing networks. These continuous streams may be mined for useful insights. In these cases, real-time analysis is crucial because of the time-sensitive nature of the interactions. However, generalizing conventional mining applications to such graphs turns out to be a challenge because of the expensive nature of graph mining algorithms. We discuss recent advances in several graph mining applications like clustering, classification, link prediction, event detection, and anomaly detection in real-time graph streams.