Traditionally, route recommendation systems focused on minimizing distance (or time) to travel between two points. However, recent attention has shifted to other factors beyond mere length. This paper addresses the challenge of ensuring a fair distribution of visits among network nodes when handling a high volume of point-to-point path queries. In doing so, we adopt a Rawlsian notion of individual-level fairness exploiting the power of randomization. Specifically, we aim to create a probabilistic distribution over paths that maximizes the minimum probability of any eligible node being included in the recommended path. A key idea of our work is the notion of forward paths , i.e., paths where travelling along any edge decreases the distance to the destination. In unweighted graphs forward paths and shortest paths coincide, but in weighted graphs forward paths provide a richer set of alternative routes, involving many more nodes while remaining close in length to the shortest path. Thus, they offer diversity and a wider basis for fairness, while maintaining near-optimal path lengths. We devise an algorithm that extracts a directed acyclic graph (DAG) containing all the forward paths in the input graph, with the same computational runtime as solving a single shortest-path query. This avoids enumerating all possible forward paths, which can be exponential in the number of nodes. We then design a flow problem on this DAG to derive the probabilistic distribution over forward paths with the desired fairness property, solvable in polynomial time through a sequence of small linear programs. Our experiments on real-world datasets validate our theoretical results, demonstrating that our technique provides individual node satisfaction while maintaining near-optimal path lengths. Moreover, our experiments show that our method can handle networks with millions of nodes and edges on a commodity laptop, and scales better than the baselines when there is a large volume of path queries for the same source and destination pair.

Dense subgraph discovery is a fundamental problem in graph mining whose goal is to extract a dense subgraph from a given graph, and it has a wide range of applications [18]. However, numerous real-world applications, ranging from computational biology and computational neuroscience to computational social science, take as input a dual graph, namely a pair of graphs on the same set of nodes. Despite the large number of such applications, research on dense subgraph discovery has focused on a single graph input, with few notable exceptions [9, 22, 35, 36]. In this work, we contribute to this line of research by studying the following novel algorithmic problem: Given a pair of graphs G, H on the same set of nodes V, how do we find a subset of nodes S ⊆ V that induces a well-connected subgraph in G and a dense subgraph in H? Our formulation generalizes previous research [11, 44, 45], by enabling to control the connectivity constraint on G. We propose a mathematical formulation and prove that it is solvable exactly in polynomial time. We compare our method to state-of-the-art competitors and find empirically that controlling the connectivity constraint enables the practitioner to obtain information that is otherwise inaccessible. Finally, we show that our proposed mining tool can be used to better understand how users interact on Twitter and connectivity aspects of human brain networks with and without Autism Spectrum Disorder (ASD).

We study a novel problem of fairness in ranking aimed at minimizing the amount of individual unfairness introduced when enforcing group-fairness constraints. Our proposal is rooted in the distributional maxmin fairness theory, which uses randomization to maximize the expected satisfaction of the worst-off individuals. We devise an exact polynomial-time algorithm to find maxmin-fair distributions of general search problems (including, but not limited to, ranking), and show that our algorithm can produce rankings which, while satisfying the given group-fairness constraints, ensure that the maximum possible value is to individuals.

Correlation clustering is arguably the most natural formulation of clustering. Given n objects and a pairwise similarity measure, the goal is to cluster the objects so that, to the best possible extent, similar objects are put in the same cluster and dissimilar objects are put in different clusters.

We study the problem of extracting a selective connector for a given set of query vertices Q subset of V in a graph G = (V,E). A selective connector is a subgraph of G which exhibits some cohesiveness property, and contains the query vertices but does not necessarily connect them all. Relaxing the connectedness requirement allows the connector to detect multiple communities and to be tolerant to outliers. We achieve this by introducing the new measure of network inefficiency and by instantiating our search for a selective connector as the problem of finding the minimum inefficiency subgraph.

Consider a multi-layered graph, where the different layers correspond to different proprietary social networks on the same ground set of users. Suppose that the owners of the different networks (called hosts) are mutually non-trusting parties: how can they compute a centrality score for each of the users using all the layers, but without disclosing information about their private graphs?

We introduce a technique to compute probably approximately correct (PAC) bounds on precision and recall for matching algorithms. The bounds require some verified matches, but those matches may be used to develop the algorithms. The bounds can be applied to network reconciliation or entity resolution algorithms, which identify nodes in different networks or values in a data set that correspond to the same entity. For network reconciliation, the bounds do not require knowledge of the network generation process.

What is the set of nodes of a social network that, under a probabilistic contagion model, would get infected if a given node $s$ gets infected? We call this set the sphere of influence of s. Due to the stochastic nature of the contagion model we need to define a notion of "expected" or "typical" cascade: this is a set of nodes which is the closest to all the possible cascades starting from s. We thus formalize the Typical Cascade problem which requires, for a given source node s, to find the set of nodes minimizing the expected Jaccard distance to all the possible cascades from s. The expected cost of a typical cascade also provides us a measure of the stability of cascade propagation, i.e., how much random cascades from a source node s deviate from the "typical" cascade. In this sense source nodes with lower expected costs are more reliable.

We study the problem of load balancing in distributed stream processing engines, which is exacerbated in the presence of skew. We introduce Partial Key Grouping (PKG), a new stream partitioning scheme that adapts the classical “power of two choices” to a distributed streaming setting by leveraging two novel techniques: key splitting and local load estimation. In so doing, it achieves better load balancing than key grouping while being more scalable than shuffle grouping. We test PKG on several large datasets, both real-world and synthetic. Compared to standard hashing, PKG reduces the load imbalance by up to several orders of magnitude, and often achieves nearly-perfect load balance. This result translates into an improvement of up to 60% in throughput and up to 45% in latency when deployed on a real Storm cluster.

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 Q ⊆ V of query vertices, find a subgraph of G that connects all query vertices and has minimum Wiener index.

We study the problem of graph summarization. Given a large graph we aim at producing a concise lossy representation that can be stored in main memory and used to approximately answer queries about the original graph much faster than by using the exact representation. In this paper we study a very natural type of summary: the original set of vertices is partitioned into a small number of super nodes connected by super edges to form a complete weighted graph. The super edge weights are the edge densities between vertices in the corresponding super nodes. The goal is to produce a summary that minimizes the reconstruction error w.r.t. The original graph. By exposing a connection between graph summarization and geometric clustering problems (i.e., k-means and k-median), we develop the first polynomial-time approximation algorithm to compute the best possible summary of a given size.

Correlation clustering is arguably the most natural formulation of clustering. Given a set of objects and a pairwise similarity measure between them, the goal is to cluster the objects so that, to the best possible extent, similar objects are put in the same cluster and dissimilar objects are put in different clusters. As it just needs a definition of similarity, its broad generality makes it applicable to a wide range of problems in different contexts, and in particular makes it naturally suitable to clustering structured objects for which feature vectors can be difficult to obtain.

We present a new randomized algorithm for estimating the number of triangles in massive graphs revealed as a stream of edges in arbitrary order. It exploits the fact that graphs arising from various domains often have small vertex covers, which enables us to reduce the space usage and sample complexity of triangle counting algorithms. The algorithm runs in four passes over the edge set and uses constant processing time per edge. We obtain precise bounds on the complexity and the approximation guarantee of our algorithm. For graphs where even the minimum vertex cover is prohibitively large, we extend the approach to achieve a trade-off between the number of passes and the space usage. Experiments on real-world graphs validate our theoretical analysis and show that the new algorithm yields more accurate estimates than state-of-the-art approaches using the same amount of space.

We study the problem of testing isomorphism (equivalence up to relabeling of the input variables) between Boolean functions. We prove the following: (1) For most functions $f:\{0,1\}^n \to \{0,1\}$, the query complexity of testing isomorphism to $f$ is $\Omega(n)$. Moreover, the query complexity of testing isomorphism to most $k$-juntas $f:\{0,1\}^n \to \{0,1\}$ is $\Omega(k)$. (2) Isomorphism to any $k$-junta $f:\{0,1\}^n \to \{0,1\}$ can be tested with $O(k \log k)$ queries. (3) For some $k$-juntas $f:\{0,1\}^n \to \{0,1\}$, testing isomorphism to $f$ with one-sided error requires $\Omega(k\log(n/k))$ queries. In particular, testing whether $f:\{0,1\}^n \to \{0,1\}$ is a $k$-parity with one-sided error requires $\Omega(k\log(n/k))$ queries. (4) The query complexity of testing isomorphism between two unknown functions $f,g:\{0,1\}^n \to \{0,1\}$ is $\widetilde{\Theta}(2^{n/2})$. These bounds are tight up to logarithmic factors, and they significantly strengthen the bounds proved by Fischer, Kindler, Ron, Safra, and Samorodnitsky [J. Comput. System Sci., 68 (2004), pp. 753--787] and Blais and O'Donnell [Proceedings of the IEEE Conference on Computational Complexity, 2010, pp. 235--246]. We also obtain results closely related to isomorphism testing, answering a question posed by Diakonikolas, Lee, Matulef, Onak, Rubinfeld, Servedio, and Wan [Proceedings of the IEEE Symposium on Foundations of Computer Science, 2007, pp. 549--558]: testing whether a function $f:\{0,1\}^n \to \{0,1\}$ can be computed by a circuit of size $\le s$ requires $s^{\Omega(1)}$ queries. All of our lower bounds apply to general (adaptive) testers.

We make a step towards characterizing the boolean functions to which isomorphism can be efficiently tested. Specifically, we prove that isomorphism to any boolean function on {0, 1}nwith a polynomial number of distinct permutations can be tested with a number of queries that is independent of n. We also show some partial results in the converse direction, and discuss related problems: testing isomorphism up to linear transformations, and testing isomorphism against a uniform (hyper)graph that is given in advance. Our results regarding the latter topic generalize a theorem of Fischer (SICOMP 2005), and in the process we also provide a simpler proof of his original result which avoids the use of Szemeredi's regularity lemma.

We study the problem of testing isomorphism (equivalence up to relabelling of the variables) of two Boolean functions f, g: {0, 1}n → {0, 1}. Our main focus is on the most studied case, where one of the functions is given (explicitly) and the other function may be queried. We prove that for every k ≤ n, the worst-case query complexity of testing isomorphism to a given k-junta is Ω(k) and O(k log k). Consequently, the query complexity of testing function isomorphism is . Prior to this work, only lower bounds of Ω(log k) queries were known, for limited ranges of k, proved by Fischer et al. (FOCS 2002), Blais and O'Donnell (CCC 2010), and recently by Alon and Blais (RANDOM 2010). The nearly tight O(k log k) upper bound improves on the upper bound from Fischer et al. (FOCS 2002). Extending the lower bound proof, we also show polynomial query-complexity lower bounds for the problems of testing whether a function can be computed by a circuit of size ≤ s, and testing whether the Fourier degree of a function is ≤ d. This answers questions posed by Diakonikolas et al. (FOCS 2007). We also address two closely related problems - 1. Testing isomorphism to a k-junta with one-sided error: we prove that for any 1 < k < n − 1, the query complexity is , which is almost optimal. This lower bound is a consequence of a proof that the query complexity of testing, with one-sided error, whether a function is a k-parity is . 2. Testing isomorphism between two unknown functions that can be queried: we prove that the query complexity in this setting is and