skip to main content


Title: The Geometry of Community Detection via the MMSE Matrix
The information-theoretic limits of community detection have been studied extensively for network models with high levels of symmetry or homogeneity. The contribution of this paper is to study a broader class of network models that allow for variability in the sizes and behaviors of the different communities, and thus better reflect the behaviors observed in real-world networks. Our results show that the ability to detect communities can be described succinctly in terms of a matrix of effective signal-to-noise ratios that provides a geometrical representation of the relationships between the different communities. This characterization follows from a matrix version of the I-MMSE relationship and generalizes the concept of an effective scalar signal-to-noise ratio introduced in previous work. We provide explicit formulas for the asymptotic per-node mutual information and upper bounds on the minimum mean-squared error. The theoretical results are supported by numerical simulations.  more » « less
Award ID(s):
1750362
NSF-PAR ID:
10139964
Author(s) / Creator(s):
; ;
Date Published:
Journal Name:
2019 IEEE International Symposium on Information Theory (ISIT)
Page Range / eLocation ID:
400 to 404
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Background Inhibitory control, or inhibition, is one of the core executive functions of humans. It contributes to our attention, performance, and physical and mental well-being. Our inhibitory control is modulated by various factors and therefore fluctuates over time. Being able to continuously and unobtrusively assess our inhibitory control and understand the mediating factors may allow us to design intelligent systems that help manage our inhibitory control and ultimately our well-being. Objective The aim of this study is to investigate whether we can assess individuals’ inhibitory control using an unobtrusive and scalable approach to identify digital markers that are predictive of changes in inhibitory control. Methods We developed InhibiSense, an app that passively collects the following information: users’ behaviors based on their phone use and sensor data, the ground truths of their inhibition control measured with stop-signal tasks (SSTs) and ecological momentary assessments (EMAs), and heart rate information transmitted from a wearable heart rate monitor (Polar H10). We conducted a 4-week in-the-wild study, where participants were asked to install InhibiSense on their phone and wear a Polar H10. We used generalized estimating equation (GEE) and gradient boosting tree models fitted with features extracted from participants’ phone use and sensor data to predict their stop-signal reaction time (SSRT), an objective metric used to measure an individual’s inhibitory control, and identify the predictive digital markers. Results A total of 12 participants completed the study, and 2189 EMAs and SST responses were collected. The results from the GEE models suggest that the top digital markers positively associated with an individual’s SSRT include phone use burstiness (P=.005), the mean duration between 2 consecutive phone use sessions (P=.02), the change rate of battery level when the phone was not charged (P=.04), and the frequency of incoming calls (P=.03). The top digital markers negatively associated with SSRT include the standard deviation of acceleration (P<.001), the frequency of short phone use sessions (P<.001), the mean duration of incoming calls (P<.001), the mean decibel level of ambient noise (P=.007), and the percentage of time in which the phone was connected to the internet through a mobile network (P=.001). No significant correlation between the participants’ objective and subjective measurement of inhibitory control was found. Conclusions We identified phone-based digital markers that were predictive of changes in inhibitory control and how they were positively or negatively associated with a person’s inhibitory control. The results of this study corroborate the findings of previous studies, which suggest that inhibitory control can be assessed continuously and unobtrusively in the wild. We discussed some potential applications of the system and how technological interventions can be designed to help manage inhibitory control. 
    more » « less
  2. Trellis based detection with pattern dependent noise prediction (PDNP) has become standard practice in the HDD industry. In a typical single-track signal processing scheme, the received samples from the read head are first filtered by a linear equalizer with a 1D partial response (PR). The linear filter output flows into a trellis-based (e.g. BCJR) detector that employs a super-trellis based on the PR mask ISI channel and a 1D pattern dependent noise prediction (1D PDNP) algorithm. The effective channel model has a media noise term which models signal dependent noise due to, e.g., magnetic grains intersected by bit boundaries. The media noise can influence two or more bit readback values. The trellis detector sends soft estimates of the coded bits to a channel decoder, which outputs estimates of the user information bits. There are two problems with traditional PDNP. First, when the number of tracks Nt simultaneously processed is greater than one, e.g. in two-dimensional magnetic recording (TDMR), the number of trellis states can become impractically large; this is the state explosion problem. Second, the relatively simple autoregressive noise model and linear prediction used in PDNP is somewhat restrictive and may not accurately represent the media noise, especially at high storage densities; this is the modeling problem. To address the state explosion problem, we separate the ISI detection and media noise prediction into two separate detectors and use the turbo-principle to exchange information between them, thus avoiding use of a super-trellis. To address the modeling problem, we design and train deep neural network (DNN) based media noise predictors. As DNN models are much more general than autoregressive models, they give a more accurate model of magnetic media noise than PDNP; this more accurate modeling results in reduced detector BERs compared to PDNP. 
    more » « less
  3. null (Ed.)
    Acoustic ranging is a technique for estimating the distance between two objects using acoustic signals, which plays a critical role in many applications, such as motion tracking, gesture/activity recognition, and indoor localization. Although many ranging algorithms have been developed, their performance still degrades significantly under strong noise, interference and hardware limitations. To improve the robustness of the ranging system, in this paper we develop a Deep learning based Ranging system, called DeepRange. We first develop an effective mechanism to generate synthetic training data that captures noise, speaker/mic distortion, and interference in the signals and remove the need of collecting a large volume of training data. We then design a deep range neural network (DRNet) to estimate distance. Our design is inspired by signal processing that ultra-long convolution kernel sizes help to combat the noise and interference. We further apply an ensemble method to enhance the performance. Moreover, we analyze and visualize the network neurons and filters, and identify a few important findings that can be useful for improving the design of signal processing algorithms. Finally, we implement and evaluate DeepRangeusing 11 smartphones with different brands and models, 4 environments (i.e., a lab, a conference room, a corridor, and a cubic area), and 10 users. Our results show that DRNet significantly outperforms existing ranging algorithms. 
    more » « less
  4. null (Ed.)
    We provide a non-asymptotic analysis of the spiked Wishart and Wigner matrix models with a generative neural network prior. Spiked random matrices have the form of a rank-one signal plus noise and have been used as models for high dimensional Principal Component Analysis (PCA), community detection and synchronization over groups. Depending on the prior imposed on the spike, these models can display a statistical-computational gap between the information theoretically optimal reconstruction error that can be achieved with unbounded computational resources and the sub-optimal performances of currently known polynomial time algorithms. These gaps are believed to be fundamental, as in the emblematic case of Sparse PCA. In stark contrast to such cases, we show that there is no statistical-computational gap under a generative network prior, in which the spike lies on the range of a generative neural network. Specifically, we analyze a gradient descent method for minimizing a nonlinear least squares objective over the range of an expansive-Gaussian neural network and show that it can recover in polynomial time an estimate of the underlying spike with a rate-optimal sample complexity and dependence on the noise level. 
    more » « less
  5. Abstract Objective

    We investigate surname affinities among areas of modern‐day China, by constructing a spatial network, and making community detection. It reports a geographical genealogy of the Chinese population that is result of population origins, historical migrations, and societal evolutions.

    Materials and methods

    We acquire data from the census records supplied by China's National Citizen Identity Information System, including the surname and regional information of 1.28 billion registered Chinese citizens. We propose a multilayer minimum spanning tree (MMST) to construct a spatial network based on the matrix of isonymic distances, which is often used to characterize the dissimilarity of surname structure among areas. We use the fast unfolding algorithm to detect network communities.

    Results

    We obtain a 10‐layer MMST network of 362 prefecture nodes and 3,610 edges derived from the matrix of the Euclidean distances among these areas. These prefectures are divided into eight groups in the spatial network via community detection. We measure the partition by comparing the inter‐distances and intra‐distances of the communities and obtain meaningful regional ethnicity classification.

    Discussion

    The visualization of the resulting communities on the map indicates that the prefectures in the same community are usually geographically adjacent. The formation of this partition is influenced by geographical factors, historic migrations, trade and economic factors, as well as isolation of culture and language. The MMST algorithm proves to be effective in geo‐genealogy and ethnicity classification for it retains essential information about surname affinity and highlights the geographical consanguinity of the population.

     
    more » « less