CoDE Publications CoDE Publications
IRIDIA Publications IRIDIA Publications
SMG Publications
WIT Publications
WIT Publications
SMG Publications
Home People Research Activities Publications Teaching Resources
By Class By Topic By Year
By Class By Topic By Year
login
R. Kumar, T. Calders, A. Gionis, and N. Tatti. Maintaining Sliding-Window Neighborhood Profiles in Interaction Networks. In A. Appice, P. Pereira Rodrigues, V. Santos Costa, J. Gama, A. Jorge, and C. Soares, editors, Proceedings of the European Conference on Machine Learning and Knowledge Discovery in Databases, ECML PKDD 2015, number 9285 in Lecture Notes in Computer Science, pages 719-735, Porto, Portugal, September 2015. Springer-Verlag.

Abstract

Large networks are being generated by applications that keep track of relationships between different data entities. Examples include online social networks recording interactions between individuals, sensor networks logging information exchanges between sensors, and more. There is a large body of literature on computing exact or approximate properties on large networks, although most methods assume static networks. On the other hand, in most modern real-world applications, networks are highly dynamic and continuous interactions along existing connections are generated. Furthermore, it is desirable to consider that old edges become less important, and their contribution to the current view of the network diminishes over time. We study the problem of maintaining the neighborhood profile of each node in an interaction network. Maintaining such a profile has applications in modeling network evolution and monitoring the importance of the nodes of the network over time. We present an online streaming algorithm to maintain neighborhood profiles in the sliding-window model. The algorithm is highly scalable as it permits parallel processing and the computation is node centric, hence it scales easily to very large networks on a distributed system, like Apache Giraph. We present results from both serial and parallel implementations of the algorithm for different social networks. The summary of the graph is maintained such that query of any window length can be performed.


Updated: 2017-03-27