Prof. Boleslaw K. Szymanski presented an invited presentation on “Challenges of Parallelizing Graph Algorithms for Network Science” at PPAM Conference.

Prof. Boleslaw K. Szymanski presented a keynote on “Challenges of Parallelizing Graph Algorithms for Network Science” at the 12th Parallel Processing and Applied Mathematics Conference in Lublin, Poland. The talk discusses the challenges of designing parallel algorithms for network science and 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. We discuss these challenges using community detection and viral news spread as examples. For community detection, we first briefly describe some interesting applications in which the algorithm designed for this application, named SpeakEasy, excels. Then we present an outline of SpeakEasy parallelization. We 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. 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. 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.