Search for: All records

Dense subgraph discovery (DSD) is a key primitive in graph mining that typically deals with extracting cliques and near-cliques. In this paper, we revisit the optimal quasi-clique (OQC) formulation for DSD and establish that it is NP--hard. In addition, we reveal the hitherto unknown property that OQC can be used to explore the entire spectrum of densest subgraphs of all distinct sizes by appropriately varying a single hyperparameter, thereby forging an intimate link with the classic densest-k-subgraph problem (DkS). We corroborate these findings on real-world graphs by applying the simple greedy algorithm for OQC with improved hyperparameter tuning, to quickly generate high-quality approximations of the size-density frontier. Our findings indicate that OQC not only extracts high quality (near)-cliques, but also large and loosely-connected subgraphs that exhibit well defined local community structure. The latter discovery is particularly intriguing, since OQC is not explicitly geared towards community detection. 

Recent work has shown that repetition coding followed by interleaving induces signal structure that can be exploited to separate multiple co-channel user transmissions, without need for pilots or coordination/synchronization between the users. This is accomplished via a statistical learning technique known as canonical correlation analysis (CCA), which works even when the channels are time-varying. Previous analysis has established that it is possible to identify the user signals up to complex scaling in the noiseless case. This letter goes one important step further to show that CCA in fact yields the linear MMSE estimate of the user signals up to complex scaling, without using any explicit training. Instead, CCA relies only on the repetition and interleaving structure. This is particularly appealing in asynchronous ad-hoc and unlicensed setups, where tight user coordination is not practical. 

In this paper, we present a method for decoding uplink messages in Internet of Things (IoT) networks that employ packet repetition. We focus on the Sigfox protocol, but our approach is applicable to other IoT protocols that employ message repetition. Our approach endeavors to enhance the reliability of message capture as well as the error rate performance at the base station. To achieve this goal, we propose a novel technique that capitalizes on the unique features of the IoT network’s uplink transmission structure. Through simulations, we demonstrate the effectiveness of our method in various scenarios, including single-user and multi-user setups. We establish the resilience of our approach under higher system loads and interference conditions, showcasing its potential to improve IoT network performance and reliability even when a large number of devices operates over limited spectrum. Our findings reveal the potential of the proposed method as a promising solution for enabling more dependable and energy-efficient communication in IoT Low Power Wide Area Networks.