We study the problem of approximately counting cliques and near-cliques in a graph, where the access to the graph is only available through crawling its vertices. This model has been introduced recently to capture real-life scenarios in which the entire graph is too massive to be stored as a whole or be scanned entirely. Sampling vertices independently is non-trivial in this model, thus algorithms which rely on sampling often use a random walk. The goal is to provide an accurate estimate by seeing only a small portion of the graph. This model is known as the random walk model or the neighborhood query model. We introduce DeMEtRIS : Dense Motif Estimation through Random Incident Sampling. This method provides a scalable algorithm for clique and near-clique counting in the random walk model. We prove the correctness of our algorithm through rigorous mathematical analysis and extensive experiments. Both our theoretical results and our experiments show that DeMEtRIS obtains a high precision estimation by only crawling a sub-linear portion on vertices. Therefore, we demonstrate a significant improvement over previous known results.

We study the problem of approximately counting cliques and near cliques in a graph, where the access to the graph is only available through crawling its vertices; thus typically seeing only a small portion of it. This model, known as the random walk model or the neighborhood query model has been introduced recently and captures real-life scenarios in which the entire graph is too massive to be stored as a whole or be scanned entirely and sampling vertices independently is non-trivial in it.

The topology of the hyperlink graph among pages expressing different opinions may influence the exposure of readers to diverse content. Structural bias may trap a reader in a 'polarized' bubble with no access to other opinions. We model readers' behavior as random walks. A node is in a 'polarized' bubble if the expected length of a random walk from it to a page of different opinion is large. The structural bias of a graph is the sum of the radii of highly-polarized bubbles. We study the problem of decreasing the structural bias through edge insertions. 'Healing' all nodes with high polarized bubble radius is hard to approximate within a logarithmic factor, so we focus on finding the best k edges to insert to maximally reduce the structural bias. We present RePBubLik, an algorithm that leverages a variant of the random walk closeness centrality to select the edges to insert. RePBubLik obtains, under mild conditions, a constant-factor approximation. It reduces the structural bias faster than existing edge-recommendation methods, including some designed to reduce the polarization of a graph.

Social networks have become an inseparable part of human life and processing them in an efficient manner is a top priority in the study of networks. These networks are highly dynamic and they are growing incessantly. Inspired by the concept of triadic closure, we propose a probabilistic mechanism to model the evolution of these dynamic graphs. Although triadic closure is ubiquitous in social networks and its presence helps forming communities, probabilistic models encapsulating it have not been studied adequately.We theoretically analyze our model and show how to bound the growth rate of some characteristics of the graph, such as degree of vertices. Leveraging our theoretical results, we develop a scheduling subroutine to process modifications o f t he graph in batches. Our scheduling subroutine is then used to speed up the state-of-the-art algorithms with negligible loss in their approximation guarantees. We demonstrate the applicability of our method by applying it to the densest subgraph discovery problem.