Source author record

Shirshendu Chatterjee

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.PR Social and Information Networks math.ST Methodology Statistics Theory Applications cond-mat.dis-nn Machine Learning math-ph math.CO math.DS math.MP physics.soc-ph

Catalog footprint

Research overview

9works

13topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Concentration inequalities for correlated network-valued processes with applications to community estimation and changepoint analysis

Network-valued time series are currently a common form of network data. However, the study of the aggregate behavior of network sequences generated from network-valued stochastic processes is relatively rare. Most of the existing research focuses on the simple setup where the networks are independent (or conditionally independent) across time, and all edges are updated synchronously at each time step. In this paper, we study the concentration properties of the aggregated adjacency matrix and the corresponding Laplacian matrix associated with network sequences generated from lazy network-valued stochastic processes, where edges update asynchronously, and each edge follows a lazy stochastic process for its updates independent of the other edges. We demonstrate the usefulness of these concentration results in proving consistency of standard estimators in community estimation and changepoint estimation problems. We also conduct a simulation study to demonstrate the effect of the laziness parameter, which controls the extent of temporal correlation, on the accuracy of community and changepoint estimation.

preprint2020arXiv

Consistent detection and optimal localization of all detectable change points in piecewise stationary arbitrarily sparse network-sequences

We consider the offline change point detection and localization problem in the context of piecewise stationary networks, where the observable is a finite sequence of networks. We develop algorithms involving some suitably modified CUSUM statistics based on adaptively trimmed adjacency matrices of the observed networks for both detection and localization of single or multiple change points present in the input data. We provide rigorous theoretical analysis and finite sample estimates evaluating the performance of the proposed methods when the input (finite sequence of networks) is generated from an inhomogeneous random graph model, where the change points are characterized by the change in the mean adjacency matrix. We show that the proposed algorithms can detect (resp. localize) all change points, where the change in the expected adjacency matrix is above the minimax detectability (resp. localizability) threshold, consistently without any a priori assumption about (a) a lower bound for the sparsity of the underlying networks, (b) an upper bound for the number of change points, and (c) a lower bound for the separation between successive change points, provided either the minimum separation between successive pairs of change points or the average degree of the underlying networks goes to infinity arbitrarily slowly. We also prove that the above condition is necessary to have consistency.

preprint2020arXiv

Estimating the treatment effect of the juvenile stay-at-home order on SARS-CoV-2 infection spread in Saline County, Arkansas

We investigate the treatment effect of the juvenile stay-at-home order (JSAHO) adopted in Saline County, Arkansas, from April 6 to May 7, in mitigating the growth of SARS-CoV-2 infection rates. To estimate the counterfactual control outcome for Saline County, we apply Difference-in-Differences and Synthetic Control design methodologies. Both approaches show that stay-at-home order (SAHO) significantly reduced the growth rate of the infections in Saline County during the period the policy was in effect, contrary to some of the findings in the literature that cast doubt on the general causal impact of SAHO with narrower scopes.

preprint2020arXiv

General Community Detection with Optimal Recovery Conditions for Multi-relational Sparse Networks with Dependent Layers

Multilayer and multiplex networks are becoming common network data sets in recent times. We consider the problem of identifying the common community structure for a special type of multilayer networks called multi-relational networks. We consider extensions of the spectral clustering methods for multi-relational networks and give theoretical guarantees that the spectral clustering methods recover community structure consistently for multi-relational networks generated from multilayer versions of both stochastic and degree-corrected block models even with dependence between network layers. The methods are shown to work under optimal conditions on the degree parameter of the networks to detect both assortative and disassortative community structures with vanishing error proportions even if individual layers of the multi-relational network has the network structures below community detectability threshold. We reinforce the validity of the theoretical results via simulations too.

preprint2015arXiv

Jigsaw percolation: What social networks can collaboratively solve a puzzle?

We introduce a new kind of percolation on finite graphs called jigsaw percolation. This model attempts to capture networks of people who innovate by merging ideas and who solve problems by piecing together solutions. Each person in a social network has a unique piece of a jigsaw puzzle. Acquainted people with compatible puzzle pieces merge their puzzle pieces. More generally, groups of people with merged puzzle pieces merge if the groups know one another and have a pair of compatible puzzle pieces. The social network solves the puzzle if it eventually merges all the puzzle pieces. For an Erdős-Rényi social network with $n$ vertices and edge probability $p_n$ , we define the critical value $p_c(n)$ for a connected puzzle graph to be the $p_n$ for which the chance of solving the puzzle equals $1/2$ . We prove that for the $n$ -cycle (ring) puzzle, $p_c(n)=Θ(1/\log n)$ , and for an arbitrary connected puzzle graph with bounded maximum degree, $p_c(n)=O(1/\log n)$ and $ω(1/n^b)$ for any $b>0$ . Surprisingly, with probability tending to 1 as the network size increases to infinity, social networks with a power-law degree distribution cannot solve any bounded-degree puzzle. This model suggests a mechanism for recent empirical claims that innovation increases with social density, and it might begin to show what social networks stifle creativity and what networks collectively innovate.

preprint2015arXiv

Multiple phase transitions in long-range first-passage percolation on square lattices

We consider a model of long-range first-passage percolation on the $d$ dimensional square lattice $Z^d$ in which any two distinct vertices $x, y \in Z^d$ are connected by an edge having exponentially distributed passage time with mean $||x-y||^{α+o(1)}$ , where $α>0$ is a fixed parameter and $||\cdot||$ is the $\ell_1$ -norm on $Z^d$ . We analyze the asymptotic growth rate of the set $B_t$ , which consists of all $x \in Z^d$ such that the first-passage time between the origin 0 and $x$ is at most $t$ , as $t\to\infty$ . We show that depending on the values of $α$ there are four growth regimes: (i) instantaneous growth for $α<d$ , (ii) stretched exponential growth for $α\in (d,2d)$ , (iii) superlinear growth for $α\in (2d,2d+1)$ and finally (iv) linear growth for $α>2d+1$ like the nearest-neighbor first-passage percolation model corresponding to $α=\infty$ .

preprint2013arXiv

A first order phase transition in the threshold- $θ\ge 2$ contact process on random $r$ -regular graphs and $r$ -trees

We consider the discrete-time threshold- $θ\ge 2$ contact process on a random r-regular graph on n vertices. In this process, a vertex with at least θoccupied neighbors at time t will be occupied at time t+1 with probability p, and vacant otherwise. We show that if $θ\ge 2$ and $r \ge θ+2$ , $ε_1$ is small and p is at least $p_1(ε_1)$ , then starting from all vertices occupied the fraction of occupied vertices stays above $1-2ε_1$ up to time $\exp(γ_1(r)n)$ with probability at least $1 - \exp(-γ_1(r)n)$ . In the other direction, we show that for $p_2 < 1$ there is an $ε_2(p_2)>0$ so that if $p \le p_2$ and the number of occupied vertices in the initial configuration is at most $ε_2(p_2)n$ , then with high probability all vertices are vacant at time $C_2(p_2) \log(n)$ . These two conclusions imply that on the random r-regular graph there cannot be a quasi-stationary distribution with density of occupied vertices between 0 and $ε_2(p_1)$ , and allow us to conclude that the process on the r-tree has a first order phase transition.

preprint2013arXiv

The order-chaos phase transition for a general class of complex Boolean networks

We consider a model for heterogeneous 'gene regulatory networks' that is a generalization of the model proposed by Chatterjee and Durrett (2011) as an "annealed approximation" of Kauffmann's (1969) random Boolean networks. In this model, genes are represented by the nodes of a random directed graph on n vertices with specified in-degree distribution (resp. out-degree distribution or joint distribution of in-degree and out-degree), and the expression bias (the expected fraction of 1's in the Boolean functions) p is same for all nodes. Following a standard practice in the physics literature, we use a discrete-time threshold contact process with parameter q=2p(1-p) (in which a vertex with at least one 'occupied' input at time t will be occupied at time t+1 with probability q, and 'vacant' otherwise) on the above random graph to approximate the dynamics of the Boolean network. We show that there is a parameter r (which can be written explicitly in terms of first few moments of the degree distribution) such that, with probability tending to 1 as n goes to infinity, if 2p(1-p)r>1, then starting from all occupied sites the threshold contact process maintains a positive ({\it quasi-stationary}) density of occupied sites for time which is exponential in n, whereas if 2p(1-p)r<1, then the persistence time of the threshold contact process is at most logarithmic in n. These two phases correspond to the 'chaotic' and 'ordered' behavior of the gene networks.

preprint2012arXiv

Asymptotic behavior of Aldous' gossip process

Aldous [(2007) Preprint] defined a gossip process in which space is a discrete $N\times N$ torus, and the state of the process at time $t$ is the set of individuals who know the information. Information spreads from a site to its nearest neighbors at rate 1/4 each and at rate $N^{-α}$ to a site chosen at random from the torus. We will be interested in the case in which $α<3$ , where the long range transmission significantly accelerates the time at which everyone knows the information. We prove three results that precisely describe the spread of information in a slightly simplified model on the real torus. The time until everyone knows the information is asymptotically $T=(2-2α/3)N^{α/3}\log N$ . If $ρ_s$ is the fraction of the population who know the information at time $s$ and $\varepsilon$ is small then, for large $N$ , the time until $ρ_s$ reaches $\varepsilon$ is $T(\varepsilon)\approx T+N^{α/3}\log (3\varepsilon /M)$ , where $M$ is a random variable determined by the early spread of the information. The value of $ρ_s$ at time $s=T(1/3)+tN^{α/3}$ is almost a deterministic function $h(t)$ which satisfies an odd looking integro-differential equation. The last result confirms a heuristic calculation of Aldous.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Shirshendu Chatterjee

Research overview

Is this your work?

9 publications

Concentration inequalities for correlated network-valued processes with applications to community estimation and changepoint analysis

Consistent detection and optimal localization of all detectable change points in piecewise stationary arbitrarily sparse network-sequences

Estimating the treatment effect of the juvenile stay-at-home order on SARS-CoV-2 infection spread in Saline County, Arkansas

General Community Detection with Optimal Recovery Conditions for Multi-relational Sparse Networks with Dependent Layers

Jigsaw percolation: What social networks can collaboratively solve a puzzle?

Multiple phase transitions in long-range first-passage percolation on square lattices

A first order phase transition in the threshold- $θ\ge 2$ contact process on random $r$ -regular graphs and $r$ -trees

The order-chaos phase transition for a general class of complex Boolean networks

Asymptotic behavior of Aldous' gossip process

See the researcher in context

Building this map preview

Shirshendu Chatterjee

Research overview

Is this your work?

9 publications

Concentration inequalities for correlated network-valued processes with applications to community estimation and changepoint analysis

Consistent detection and optimal localization of all detectable change points in piecewise stationary arbitrarily sparse network-sequences

Estimating the treatment effect of the juvenile stay-at-home order on SARS-CoV-2 infection spread in Saline County, Arkansas

General Community Detection with Optimal Recovery Conditions for Multi-relational Sparse Networks with Dependent Layers

Jigsaw percolation: What social networks can collaboratively solve a puzzle?

Multiple phase transitions in long-range first-passage percolation on square lattices

A first order phase transition in the threshold-θ≥2θ\ge 2θ≥2 contact process on random rrr-regular graphs and rrr-trees

The order-chaos phase transition for a general class of complex Boolean networks

Asymptotic behavior of Aldous' gossip process

See the researcher in context

Building this map preview

A first order phase transition in the threshold- $θ\ge 2$ contact process on random $r$ -regular graphs and $r$ -trees