On Monday, December 14 at 6:45, our MSc programme will have the pleasure of hosting online Professors Evi Pitoura and Panayiotis Tsaparas from the Department of Computer Science & Engineering of the University of Ioannina, who will be giving two guest lectures on “Finding lasting dense subgraphs” and “Fairness Aware PageRank” respectively.
Zoom link: https://authgr.zoom.us/j/97159727135?pwd=VzQ0bGYzNlcwUVQzZFlwa1pkV2dwZz09
Meeting ID: 971 5972 7135 Passcode: 944414
Finding lasting dense subgraphs: Graphs form a natural model for relationships and interactions between entities, for example, between people in social and cooperation networks, servers in computer networks, or tags and words in documents and tweets. But, which of these relationships or interactions are the most lasting ones? In this paper, we study the following problem: given a set of graph snapshots, which may correspond to the state of an evolving graph at different time instances, identify the set of nodes that are the most densely connected in all snapshots. We call this problem the Best Friends Forever (BFF) problem. We provide definitions for density over multiple graph snapshots, that capture different semantics of connectedness over time, and we study the corresponding variants of the BFF problem. We then look at the On–Off BFF (O2BFF) problem that relaxes the requirement of nodes being connected in all snapshots, and asks for the densest set of nodes in at least k of a given set of graph snapshots. We show that this problem is NP-complete for all definitions of density, and we propose a set of efficient algorithms. Finally, we present experiments with synthetic and real datasets that show both the efficiency of our algorithms and the usefulness of the BFF and the O2BFF problems.
Konstantinos Semertzidis, Evaggelia Pitoura, Evimaria Terzi, Panayiotis Tsaparas: Finding lasting dense subgraphs. Data Min. Knowl. Discov. 33(5): 1417-1445 (2019) (PKDD 2019 Track)
Fairness Aware PageRank: Algorithmic fairness has attracted significant attention in the past years. Most work has focused on supervised learning problems, such as classification, or regression. In this work, we consider
fairness for link analysis algorithms, where given a network the goal is to determine the relative importance of the nodes in the network by exploiting the structure of the graph. More specifically, we focus on the celebrated PageRank algorithm. We provide definitions for fairness, and algorithms for achieving fairness, while maintaining the utility of the PageRank algorithm. We present experiments with real and synthetic data that study the trade-off between fairness and utility.
Sotiris Tsioutsiouliklis, Evaggelia Pitoura, Panayiotis Tsaparas, Ilias Kleftakis and Nikos Mamoulis: Fairness Aware PageRank (2020) (under submission, preliminary version: CoRR abs/2005.14431)