Detecting antagonistic near-balanced dense subgraphs is a crucial problem for community search and conflict detection in graph and network analysis, which has wide applications in social media analysis, business, geopolitics etc. To tackle the absence of a unified definition of antagonistic situation, we propose theantagonismmeasure, which quantifies the quality of subgraphs by three dimensions: polarity, internal cohesion, and external antagonistic normalized density. Inspired by the contribution of small antagonistic balanced patterns to antagonism and balance, this paper introduces an efficient algorithmic framework to mine locally specific pattern densest subgraph structure to find subgraphs with high antagonism. We in particular jointly consider$hx$-pattern compact number and L$hx$PDS and design a new Iterative Propose-Prune-and-Verify pipeline in signed graphs (IPPV-s) for top-$k$L$hx$PDS detection. The key contributions are: (1) The antagonism measure is defined, bridging the gap between structural density and balance theory. (2) An efficient algorithmic pipeline that combines convex optimization with maximum flow verification is proposed, which enables scalable and efficient antagonistic near-balanced dense subgraph discovery. (3) Extensive experiments on real signed network datasets show the effectiveness of our approach in uncovering meaningful subgraphs that capture both cooperative and conflicting dynamics.

The Budget Limited Coreness Maximization (BLCM) problem aims to enhance average user engagement by activating a limited number of connections, i.e., inserting up to b edges to maximize the coreness gain of all vertices in a graph. Due to the cascading feature, we prove the BLCM is NP-hard, APX-hard, and not submodular, meaning greedy sequential edge insertion fails to deliver satisfactory results. As a result, solving BLCM requires combinatorial edge insertion and must face the combinatorial exploration difficulty. This paper proposes the first effective and polynomial-time approach to BLCM. It embeds local combinatorial optimization into global greedy search to boost the benefits of combinatorial optimization while restricting its complexity. Specifically, we propose efficient methods to evaluate the cascaded coreness improvements of two local combinatorial strategies, i.e., when a leader or a group of nodes increase their coreness values via local edge insertion. Note that the key difficulty lies in evaluating the cascading effects. Based on these, we propose three efficient combinatorial edge insertion strategies: (1) Leader-Centric Greedy Insertion (LCGI), (2) Group-Centric Greedy Insertion (GCGI), and (3) a Leader-Group Balance (LGB) insertion. LCGI greedily finds the most influential leader that can produce the highest coreness gain together with its followers. GCGI finds the most influential group that can promote the most coreness gain. LGB combines the two strategies to select edge combinations adaptively. We prove the low complexity of LCGI, GCGI and LGB. Experiments conducted on 13 real-world datasets highlight their practical utility and superiority over existing approaches.

Bottom-up k-vertex connected component (k- VCC) enumeration methods, referred to as VCCE-BU, have exhib-ited better efficiency compared to the exact top-down k- VCC enumeration method (VCCE-TD). However, VCCE-BU has been found to have surprisingly low detection accuracy, that it may detect fewer k- VCC vertices than VCCE-TD. This raises the question of what causes VCCE-BU to have a low k-VCC enumeration quality. This paper investigates the reason and proposes that the local expansion should be reformulated as a Multiple vertex collaborative Expansion problem instead of the traditional Unitary Expansion (UE). A Multiple Expansion (ME) approach, which allows to expand multiple neighboring vertices jointly and collaboratively is proposed, which is proven exact in local expansion. However, the exact ME-based local expansion needs to explore large neighborhoods in each step, which is time-consuming. To address the efficiency issue, a Ring-based Multiple Expansion (RME) is proposed to conduct ME within one-hop neighbors. A maximum flow-based merging algorithm FBM is proposed for effective merging. A maximal clique and breath-first-search-based quick seeding algorithm QkVCS is proposed to generate k-VCC seeds efficiently. As a result, RIPPLE which integrates QkVCS+FBM+RME is presented as a new accurate and efficient bottom-up approach. Extensive verifications in real large-scale graph datasets demonstrate that even the single-thread RIPPLE is much more accurate and a magnitude faster than the state-of-the-art VCCE-BU method. We also demonstrate the effective speeding up to run RIPPLE in parallel.

Detecting locally, non-overlapping, near-clique densest subgraphs is a crucial problem for community search in social networks. As a vertex may be involved in multiple overlapped local cliques, detecting locally densest sub-structures considering h -clique density, i.e., locally h-clique densest subgraph (LhCDS) attracts great interests. This paper investigates the L h CDS detection problem and proposes an efficient and exact algorithm to list the top- k non-overlapping, locally h -clique dense, and compact subgraphs. We in particular jointly consider h -clique compact number and L h CDS and design a new ''Iterative Propose-Prune-and-Verify'' pipeline (IPPV) for top- k L h CDS detection. (1) In the proposal part, we derive initial bounds for h -clique compact numbers; prove the validity, and extend a convex programming method to tighten the bounds for proposing L h CDS candidates without missing any. (2) Then a tentative graph decomposition method is proposed to solve the challenging case where a clique spans multiple subgraphs in graph decomposition. (3) To deal with the verification difficulty, both a basic and a fast verification method are proposed, where the fast method constructs a smaller-scale flow network to improve efficiency while preserving the verification correctness. The verified L h CDSes are returned, while the candidates that remained unsure reenter the IPPV pipeline. (4) We further extend the proposed methods to locally more general pattern densest subgraph detection problems. We prove the exactness and low complexity of the proposed algorithm. Extensive experiments on real datasets show the effectiveness and high efficiency of IPPV. Codes are available at: https://github.com/Elssky/IPPV

Ranging-based localization is a fundamental problem in the Internet of Things and unmanned aerial vehicle networks. However, the nodes’ limited-ranging scope and users’ broad coverage purpose inevitably cause network sparsity or subnetwork sparsity. The performances of existing localization algorithms are extremely unsatisfactory in sparse networks. A crucial way to deal with the sparsity is to exploit the hidden knowledge provided by the unmeasured edges, which inspires this work to propose a hypothesis-based Joint Edge Inference and Localization algorithm called InferLoc . InferLoc mines the Unmeasured but Inferable Edges (UIEs). Each UIE is an unmeasured edge, but it is restricted through other edges in the network to be inside a rigid component, so it has only a limited number of possible lengths. We propose an efficient method to detect UIEs and geometric approaches to infer possible lengths for UIEs in 2D and 3D networks. The inferred possible lengths of UIEs are then treated as multiple hypotheses to determine the node locations and the lengths of UIEs simultaneously through a joint graph optimization process. In the joint graph optimization model, to make the 0/1 decision variables for hypotheses selection differentiable, differentiable functions are proposed to relax the 0/1 selections, and rounding is applied to select the final length after the optimization converges. We also prove the condition when a UIE can contribute to sparse localization. Extensive experiments show remarkably better accuracy and efficiency performances of InferLoc than the state-of-the-art network localization algorithms. In particular, it reduces the localization errors by more than 90% and speeds up the convergence time more than 100 times than that of the widely used G2O-based methods in sparse networks.

In this paper, we study the problem of on-demand food delivery in a new setting where two groups of workers -- riders and taxi drivers (drivers for short) -- cooperate with each other for better service. The riders are responsible for the first and the last mile, and the drivers are in charge of the cross-community transportation. We show this problem is generally NP-hard by a reduction from the well-known 3-dimensional matching (3DM). To tackle with this problem, we first reduce it to the maximum independent set problem and use a simple greedy strategy to design an approximate algorithm which has a polynomial time. Considering the exponents in the polynomial are not very small, we then transform the 3DM into two rounds of 2-dimensional matching and propose a fast algorithm to solve it. Though 3DM problem is NP-hard, we find the cooperation between riders and drivers form a special tripartite graph, based on which we construct a flow network and employ the min-cost max-flow algorithm to efficiently compute the exact solution. We conduct extensive experiments to show the efficiency and the effectiveness of our proposed algorithms.