A Fast Community-based Approach for Discovering Anomalies in Evolutionary Networks

Many real-life networks such as social networks, biological networks, citation networks etc., are temporally evolving by nature. In general, the evolution takes place gradually with time. But occasionally, the nodes may exhibit anomalous behavior that is to be detected and reported in real time. In this work, for anomaly detection in evolutionary networks, an action based approach is followed taking into account the network topology. The network is represented as a temporal stream of weighted graphs, where edge weights stand for frequency or power of actions. A new definition of anomaly score is introduced for nodes based on its action history. To reduce the search space, the community structure of the graph is exploited. It has been shown that only the nodes having multiple community membership are enough to detect anomaly in a temporally evolving network with overlapping community structure. To the best of our knowledge, this is the first work to exploit the overlapping community structure of an evolutionary network to identify the graph snapshots containing anomalous events. Experimental studies on both synthetic and real-world evolutionary networks show that the proposed technique achieves almost 16% improvement in F-Score compared to the state-of-the-art algorithms. Moreover, parallel implementation of the proposed technique results nearly 10× speedup making it suitable for real time computation of anomaly in evolutionary networks.