Maintaining sliding-window neighborhood profiles in interaction networks

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 net- works. On the other hand, in most modern real-world applications, net- works are highly dynamic and continuously 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. We present results from both serial and parallel implementations of the algorithm for different social networks.
Authors Name: 
Rohit Kumar
Toon Calders
Gionis Aristides
Tatti Nikolaj
S.I. 2014: 
Thursday, September 10, 2015 - 15:50 to 16:15