Postdoc, University of Southern California
Email
Abstract
The Minimum Wiener Connector
The Wiener index of a graph is the sum of all pairwise shortest-path distances between its vertices. In this paper we study the novel problem of finding a minimum Wiener connector: given a connected graph G=(V,E) and a set of query vertices Q, find a subgraph of G that connects all query vertices and has minimum Wiener index.
We show that The Minimum Wiener Connector admits a polynomial-time (albeit impractical) exact algorithm for the special case where the number of query vertices is bounded. We show that in general the problem is NP-hard, and has no PTAS unless P=NP. Our main contribution is a constant-factor approximation algorithm running in time O(|Q||E|).
A thorough experimentation on a large variety of real-world graphs confirms that our method returns smaller and denser solutions than other methods, and does so by adding to the query set Q a small number of important vertices (i.e., vertices with high centrality).
Bio
Natali is a postdoc with the Melady Machine Learning Lab in the computer science department at the University of Southern California. Prior to joining USC, Natali received her PhD with the data mining group at Boston University, where her thesis was on structural matrix completion.
Overall, Natali’s research is centered around algorithmic aspects of data mining and machine learning for large datasets. She focuses on integrating theoretical results with practical algorithms to tackle challenges that arise with real-world messy data, such as missing information, noise, and lack of structure; whether it be in a matrix, tensor, graph, or so on.
Her work has application across a wide range of areas including recommender systems, biology, neuroscience, social networks, urban informatics, and misinformation.
Aside from problem solving and mathematics, Natali also loves photography and painting.