Wydarzenia » Challenges of Parallelizing Graph Algorithms for Network Science – wykład prof. Bolesława Szymańskiego

During the talk the challenges of designing parallel algorithms for network science and especially for network analysis will be discussed. The rapid growth of the volume of data collected from networks fuels the urgency of using parallel processing to provide timely network analysis. The main challenge in creating the needed parallel solutions is the network connectivity. In many physical world simulations interacting components are located close to each other, and computational stencils are regular. In contrast, social, biological, and some other types of networks allow for distant and irregularly structured communication. Consequently, partitioning of such networks for parallel processing is challenging and often invokes heavy communication overhead. It is especially so for networks which represent social interactions or biological processes at different levels of abstraction. I discuss these challenges using community detection as an example.

I will start with the GANXiS algorithm that I designed for social network analysis and will show how it was efficiently parallelized on two different parallel architectures. Then, I will discuss GANXiS extensions to bio-medical networks which require combining local metrics employed by GANXiS with global metrics useful in bio-medical networks. First, I will briefly describe some interesting applications in which the resulting algorithm, named SpeakEasy, excels. Then I will present an outline of SpeakEasy parallelization.
I will also propose a scalable parallel algorithm to derive the node embedding to better understand the information dissemination patterns and predict emergent cascades of viral events in online media. Previous solutions concentrate on modeling the links of information propagation. In contrast the given algorithm infers the topic-specific output influence and the input selectivity of nodes. The parallel algorithm iteratively merges local node embedding in particular communities to obtain the global optimal results so that the processing of cascades can be significantly accelerated. Based on the obtained latent representation of nodes, the emergent cascades of viral news events in online media can be successfully predicted with 80% accuracy at its early stage. Experimental results show that our parallel inference algorithm achieves a 50-fold speedup and requires a low communication overhead, while the accuracy of the cascade size prediction is preserved.

Bio of the Presenter:

Dr. Boleslaw K. Szymanski is the Claire and Roland Schmitt Distinguished Professor of Computer Science and a Professor of Cognitive Science at RPI. He is the Founding Director of the ARL Social and Cognitive Networks Academic Research Center and of the RPI NEST Center. He received Ph.D. in Computer Science from National Academy of Sciences in Warsaw, in 1976. He published over 400 scientific articles, is a foreign member of the National Academy of Science in Poland, an IEEE Fellow, and a National Lecturer for the ACM. In 2009, he received the Wilkes Medal of British Computer Society and in 2003 the Willey Distinguished Faculty Award from RPI. His current research interests focus on network science and computer and social networks.