Skip to main content
Department of Information Technology

Sparsification of probabilistic networks

Networks are one of the main models used to study complex systems. From protein interactions in biological systems to social relationships among people, from functional correlations in brain activity to links in transportation systems or the Web, the connections between entities are often as important as the individual properties of each entity in defining the structure and behavior of the system. However, it is often difficult to know with certainty whether two entities are connected, and this uncertainty can be represented using probabilistic networks where a probability of existence is associated to each edge.

Probabilistic networks are complex to analyse. Therefore, the objective of this project is to implement and test a recent sparsification algorithm. A network sparsification algorithm generates a smaller network preserving structural properties of the original data, to increase the efficiency of the analysis. A recent algorithm from the literature will be implemented and tested on both real and synthetic data, to study its efficiency and effectiveness. The candidate must have knowledge of programming in C++.

The article on which this project is based is: P. Parchas, N. Papailiou, D. Papadias and F. Bonchi, "Uncertain Graph Sparsification," in IEEE Transactions on Knowledge and Data Engineering, vol. 30, no. 12, pp. 2435-2449, 1 Dec. 2018.

Supervisors: Amin Kaveh (amin.kaveh@it.uu.se) and Matteo Magnani (matteo.magnani@it.uu.se)

Updated  2019-10-19 21:21:37 by Maya Neytcheva.