Title:	ADAG: Algorithmic Data Analysis on Graphs
DNr:	NAISS 2023/22-835
Project Type:	NAISS Small Compute
Principal Investigator:	Lutz Oettershagen <lutzo@kth.se>
Affiliation:	Kungliga Tekniska högskolan
Duration:	2023-08-23 – 2024-09-01
Classification:	10201
Keywords:

Abstract

Our project aims to analyze large-scale static and dynamic networks to understand their properties and obtain new knowledge about the underlying dynamics. Prominent real-world examples are dynamic social networks, in which participants build and end friendships over time, communication networks like email networks, in which emails correspond to instantaneous connections between users; or human contact networks modeling face-to-face contacts. Due to the ongoing explosive growth and availability of (time-stamped) structured data, there is a future need for automated knowledge extraction from large-scale and dynamic graph data sets. In our project, we will design and analyze methods for obtaining knowledge from such networks. The main goal is to obtain deeper insights into hidden or unknown structures and properties of large-scale real-world (temporal) networks and underlying processes by developing efficient and effective algorithms. To this end, we will implement and use new data mining algorithms; more specifically, our project will focus on two main areas: 1. Network decomposition and fair communities: Analyzing networks is challenging, especially if an additional time dimension can lead to higher complexity than conventional static graphs. One popular way of tackling complex challenges in networks, in general, is to decompose networks to obtain smaller components containing important information for the task at hand. However, such decompositions need to consider networks' properties to lead to meaningful results. Our project proposes a new decomposition for dynamic networks that considers temporal constraints. In the case of static networks, fairness constraints for identifying communities defined by dense subgraphs were recently proposed. Based on these previous results, we plan to extend these constraints and computational methods for novel and sensible definitions of fairness. 2. Group centralities in dynamic networks: Measuring the centrality of nodes in a network is a cornerstone of network analysis. The goal is to determine the importance of nodes in the network and find the most central ones. Various concepts of centrality have been proposed, and their informative value must be assessed based on a given research question. However, many classical and recent centrality measures focus only on static graphs and on determining the importance of single nodes. In our project, we aim to extend these works to dynamic networks and groups of nodes, as we often are interested in more than a single node that maximizes a notion of importance, e.g., we want to know the k persons that together have the highest influence in the network. To keep up with the large-scale sizes of real-world networks and to track changes over time, parts of our project will focus on (distributed) streaming algorithms operating on a variable-sized time window of the edge streams. This way, we can handle large, possibly infinite long, streams of incoming time-stamped edges and capture the drift of local or global graph properties, e.g., track the importance or strength of groups of nodes over time or identify changes of fairness and structure of communities caused by leaving and joining members.