An official website of the United States government
We consider the following question. We have a dense regular graph $$G$$ with degree $$\a n$$, where $$\a>0$$ is a constant. We add $m=o(n^2)$ random edges. The edges of the augmented graph $G(m)$ are given independent edge weights $$X(e),e\in E(G(m))$$. We estimate the minimum weight of some specified combinatorial structures. We show that in certain cases, we can obtain the same estimate as is known for the complete graph, but scaled by a factor $$\a^{-1}$$. We consider spanning trees, shortest paths and perfect matchings in (pseudo-random) bipartite graphs.
more »
« less
RePBubLik: Reducing Polarized Bubble Radius with Link Insertions
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.
more »
« less
- PAR ID:
- 10273589
- Editor(s):
- Liane, Lewin-Eytan; David, Carmel; Elad, Yom-Tov
- Date Published:
- Journal Name:
- WSDM
- Volume:
- 2021
- Page Range / eLocation ID:
- 139 to 147
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Pesticides benefit agriculture by increasing crop yield, quality, and security. However, pesticides may inadvertently harm bees, which are valuable as pollinators. Thus, candidate pesticides in development pipelines must be assessed for toxicity to bees. Leveraging a dataset of 382 molecules with toxicity labels from honey bee exposure experiments, we train a support vector machine (SVM) to predict the toxicity of pesticides to honey bees. We compare two representations of the pesticide molecules: (i) a random walk feature vector listing counts of length- L walks on the molecular graph with each vertex- and edge-label sequence and (ii) the Molecular ACCess System (MACCS) structural key fingerprint (FP), a bit vector indicating the presence/absence of a list of pre-defined subgraph patterns in the molecular graph. We explicitly construct the MACCS FPs but rely on the fixed-length- L random walk graph kernel (RWGK) in place of the dot product for the random walk representation. The L-RWGK-SVM achieves an accuracy, precision, recall, and F1 score (mean over 2000 runs) of 0.81, 0.68, 0.71, and 0.69, respectively, on the test data set—with L = 4 being the mode optimal walk length. The MACCS-FP-SVM performs on par/marginally better than the L-RWGK-SVM, lends more interpretability, but varies more in performance. We interpret the MACCS-FP-SVM by illuminating which subgraph patterns in the molecules tend to strongly push them toward the toxic/non-toxic side of the separating hyperplane.more » « less
-
Everyone puts things off sometimes. How can we combat this tendency to procrastinate? A well-known technique used by instructors is to break up a large project into more manageable chunks. But how should this be done best? Here we study the process of chunking using the graph-theoretic model of present bias introduced by Kleinberg and Oren [2014]. We first analyze how to optimally chunk single edges within a task graph, given a limited number of chunks. We show that for edges on the shortest path, the optimal chunking makes initial chunks easy and later chunks progressively harder. For edges not on the shortest path, optimal chunking is significantly more complex, but we provide an efficient algorithm that chunks the edge optimally. We then use our optimal edge-chunking algorithm to optimally chunk task graphs. We show that with a linear number of chunks on each edge, the biased agent’s cost can be exponentially lowered, to within a constant factor of the true cheapest path. Finally, we extend our model to the case where a task designer must chunk a graph for multiple types of agents simultaneously. The problem grows significantly more complex with even two types of agents, but we provide optimal graph chunking algorithms for two types. Our work highlights the efficacy of chunking as a means to combat present bias.more » « less
-
In this paper we study the randomly edge colored graph that is obtained by adding randomly colored random edges to an arbitrary randomly edge colored dense graph. In particular we ask how many colors and how many random edges are needed so that the resultant graph contains a fixed number of edge disjoint rainbow Hamilton cycles w.h.p. We also ask when in the resultant graph every pair of vertices is connected by a rainbow path w.h.p.more » « less
-
Abstract We show that for every integer and large , every properly edge‐colored graph on vertices with at least edges contains a rainbow subdivision of . This is sharp up to a polylogarithmic factor. Our proof method exploits the connection between the mixing time of random walks and expansion in graphs.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1145/3437963.3441825
