Networks, which represent agents and interactions between them, arise in myriad applications throughout the sciences, engineering, and even the humanities. To understand large-scale structure in a network, a common task is to cluster a network's nodes into sets called "communities", such that there are dense connections within communities but sparse connections between them. A popular and statistically principled method to perform such clustering is to use a family of generative models known as stochastic block models (SBMs). In this paper, we show that maximum likelihood estimation in an SBM is a network analog of a well-known continuum surface-tension problem that arises from an application in metallurgy. To illustrate the utility of this relationship, we implement network analogs of three surface-tension algorithms, with which we successfully recover planted community structure in synthetic networks and which yield fascinating insights on empirical networks that we construct from hyperspectral videos.

Networks capture pairwise interactions between entities and are frequently used in applications such as social networks, food networks, and protein interaction networks, to name a few. Communities, cohesive groups of nodes, often form in these applications, and identifying them gives insight into the overall organization of the network. One common quality function used to identify community structure is modularity. In Hu et al. [SIAM J. Appl. Math., 73 (2013), pp. 2224-2246], it was shown that modularity optimization is equivalent to minimizing a particular nonconvex total variation (TV) based functional over a discrete domain. They solve this problem-assuming the number of communities is known-using a Merriman-Bence-Osher (MBO) scheme. We show that modularity optimization is equivalent to minimizing a convex TV-based functional over a discrete domain-again, assuming the number of communities is known. Furthermore, we show that modularity has no convex relaxation satisfying certain natural conditions. We therefore find a manageable nonconvex approximation using a Ginzburg-Landau functional, which provably converges to the correct energy in the limit of a certain parameter. We then derive an MBO algorithm that has fewer hand-tuned parameters than in Hu et al. and that is seven times faster at solving the associated diffusion equation due to the fact that the underlying discretization is unconditionally stable. Our numerical tests include a hyperspectral video whose associated graph has 2.9× 107 edges, which is roughly 37 times larger than what was handled in the paper of Hu et al.

BACKGROUND: First-line chemotherapy for patients with cisplatin-ineligible locally advanced or metastatic urothelial carcinoma is associated with short response duration, poor survival, and high toxicity. This study assessed atezolizumab (anti-programmed death-ligand 1 [PD-L1]) as treatment for metastatic urothelial cancer in cisplatin-ineligible patients. METHODS: For this single-arm, multicentre, phase 2 study, in 47 academic medical centres and community oncology practices in seven countries in North America and Europe, we recruited previously untreated patients with locally advanced or metastatic urothelial cancer who were cisplatin ineligible. Patients were given 1200 mg intravenous atezolizumab every 21 days until progression. The primary endpoint was independently confirmed objective response rate per Response Evaluation Criteria in Solid Tumors version 1.1 (central review), assessed in prespecified subgroups based on PD-L1 expression and in all patients. All participants who received one or more doses of atezolizumab were included in the primary and safety analyses. This study was registered with ClinicalTrials.gov, number NCT02108652. FINDINGS: Between June 9, 2014, and March 30, 2015, we enrolled 123 patients, of whom 119 received one or more doses of atezolizumab. At 17·2 months median follow-up, the objective response rate was 23% (95% CI 16 to 31), the complete response rate was 9% (n=11), and 19 of 27 responses were ongoing. Median response duration was not reached. Responses occurred across all PD-L1 and poor prognostic factor subgroups. Median progression-free survival was 2·7 months (2·1 to 4·2). Median overall survival was 15·9 months (10·4 to not estimable). Tumour mutation load was associated with response. Treatment-related adverse events that occurred in 10% or more of patients were fatigue (36 [30%] patients), diarrhoea (14 [12%] patients), and pruritus (13 [11%] patients). One treatment-related death (sepsis) occurred. Nine (8%) patients had an adverse event leading to treatment discontinuation. Immune-mediated events occurred in 14 (12%) patients. INTERPRETATION: Atezolizumab showed encouraging durable response rates, survival, and tolerability, supporting its therapeutic use in untreated metastatic urothelial cancer. FUNDING: F Hoffmann-La Roche, Genentech.