Online two-sided matching markets such as Q&A forums (e.g. StackOverflow, Quora) and online labour platforms (e.g. Upwork) critically rely on the ability to propose adequate matches based on imperfect knowledge of the two parties to be matched. This prompts the following question: Which matching recommendation algorithms can, in the presence of such uncertainty, lead to efficient platform operation? To answer this question, we develop a model of a task / server matching system. For this model, we give a necessary and sufficient condition for an incoming stream of tasks to be manageable by the system. We further identify a so-called back-pressure policy under which the throughput that the system can handle is optimized. We show that this policy achieves strictly larger throughput than a natural greedy policy. Finally, we validate our model and confirm our theoretical findings with experiments based on logs of Math.StackExchange, a StackOverflow forum dedicated to mathematics.

Motivated by community detection, we characterise the spectrum of the non-backtracking matrix $B$ in the Degree-Corrected Stochastic Block Model. Specifically, we consider a random graph on $n$ vertices partitioned into two equal-sized clusters. The vertices have i.i.d. weights $\{ \phi_u \}_{u=1}^n$ with second moment $\Phi^{(2)}$. The intra-cluster connection probability for vertices $u$ and $v$ is $\frac{\phi_u \phi_v}{n}a$ and the inter-cluster connection probability is $\frac{\phi_u \phi_v}{n}b$. We show that with high probability, the following holds: The leading eigenvalue of the non-backtracking matrix $B$ is asymptotic to $\rho = \frac{a+b}{2} \Phi^{(2)}$. The second eigenvalue is asymptotic to $\mu_2 = \frac{a-b}{2} \Phi^{(2)}$ when $\mu_2^2 > \rho$, but asymptotically bounded by $\sqrt{\rho}$ when $\mu_2^2 \leq \rho$. All the remaining eigenvalues are asymptotically bounded by $\sqrt{\rho}$. As a result, a clustering positively-correlated with the true communities can be obtained based on the second eigenvector of $B$ in the regime where $\mu_2^2 > \rho.$ In a previous work we obtained that detection is impossible when $\mu_2^2 < \rho,$ meaning that there occurs a phase-transition in the sparse regime of the Degree-Corrected Stochastic Block Model. As a corollary, we obtain that Degree-Corrected Erd\H{o}s-R\'enyi graphs asymptotically satisfy the graph Riemann hypothesis, a quasi-Ramanujan property. A by-product of our proof is a weak law of large numbers for local-functionals on Degree-Corrected Stochastic Block Models, which could be of independent interest.

We consider a Degree-Corrected Planted-Partition model: a random graph on $n$ nodes with two asymptotically equal-sized clusters. The model parameters are two constants $a,b > 0$ and an i.i.d. sequence of weights $(\phi_u)_{u=1}^n$, with finite second moment $\Phi^{(2)}$. Vertices $u$ and $v$ are joined by an edge with probability $\frac{\phi_u \phi_v}{n}a$ when they are in the same class and with probability $\frac{\phi_u \phi_v}{n}b$ otherwise. We prove that it is information-theoretically impossible to estimate the spins in a way positively correlated with the true community structure when $(a-b)^2 \Phi^{(2)} \leq 2(a+b)$. A by-product of our proof is a precise coupling-result for local-neighbourhoods in Degree-Corrected Planted-Partition models, which could be of independent interest.