BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Harry Crane

Harry Crane contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
math.PRmath.STStatistics Theorymath.LOmath.COMethodologyphysics.soc-phSocial and Information NetworksComputationMachine Learning

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
17works
0followers
10topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

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

Published work

17 published item(s)

preprint2021arXiv

Inference on the History of a Randomly Growing Tree

The spread of infectious disease in a human community or the proliferation of fake news on social media can be modeled as a randomly growing tree-shaped graph. The history of the random growth process is often unobserved but contains important information such as the source of the infection. We consider the problem of statistical inference on aspects of the latent history using only a single snapshot of the final tree. Our approach is to apply random labels to the observed unlabeled tree and analyze the resulting distribution of the growth process, conditional on the final outcome. We show that this conditional distribution is tractable under a shape-exchangeability condition, which we introduce here, and that this condition is satisfied for many popular models for randomly growing trees such as uniform attachment, linear preferential attachment and uniform attachment on a $D$-regular tree. For inference of the root under shape-exchangeability, we propose O(n log n) time algorithms for constructing confidence sets with valid frequentist coverage as well as bounds on the expected size of the confidence sets. We also provide efficient sampling algorithms that extend our methods to a wide class of inference problems.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Relative exchangeability with equivalence relations

We describe an Aldous--Hoover-type characterization of random relational structures that are exchangeable relative to a fixed structure which may have various equivalence relations. Our main theorem gives the common generalization of the results on relative exchangeability due to Ackerman \cite{Ackerman2015} and Crane and Towsner \cite{CraneTowsner2015} and hierarchical exchangeability results due to Austin and Panchenko \cite{AustinPanchenko2014}.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

The structure of combinatorial Markov processes

Every exchangeable Feller process taking values in a suitably nice combinatorial state space can be constructed by a system of iterated random Lipschitz functions. In discrete time, the construction proceeds by iterated application of independent, identically distributed functions, while in continuous time the random functions occur as the atoms of a time homogeneous Poisson point process. We further show that every exchangeable Feller process projects to a Feller process in an appropriate limit space, akin to the projection of partition-valued processes into the ranked-simplex and graph-valued processes into the space of graph limits. Together, our main theorems establish common structural features shared by all exchangeable combinatorial Feller processes, regardless of the dynamics or resident state space, thereby generalizing behaviors previously observed for exchangeable coalescent and fragmentation processes as well as other combinatorial stochastic processes. If, in addition, an exchangeable Feller process evolves on a state space satisfying the $n$-disjoint amalgamation property for all $n\geq1$, then its jump measure can be decomposed explicitly in the sense of Lévy--Itô--Khintchine.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Atypical scaling behavior persists in real world interaction networks

Scale-free power law structure describes complex networks derived from a wide range of real world processes. The extensive literature focuses almost exclusively on networks with power law exponent strictly larger than 2, which can be explained by constant vertex growth and preferential attachment. The complementary scale-free behavior in the range between 1 and 2 has been mostly neglected as atypical because there is no known generating mechanism to explain how networks with this property form. However, empirical observations reveal that scaling in this range is an inherent feature of real world networks obtained from repeated interactions within a population, as in social, communication, and collaboration networks. A generative model explains the observed phenomenon through the realistic dynamics of constant edge growth and a positive feedback mechanism. Our investigation, therefore, yields a novel empirical observation grounded in a strong theoretical basis for its occurrence.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Community detection for interaction networks

In many applications, it is common practice to obtain a network from interaction counts by thresholding each pairwise count at a prescribed value. Our analysis calls attention to the dependence of certain methods, notably Newman--Girvan modularity, on the choice of threshold. Essentially, the threshold either separates the network into clusters automatically, making the algorithm's job trivial, or erases all structure in the data, rendering clustering impossible. By fitting the original interaction counts as given, we show that minor modifications to classical statistical methods outperform the prevailing approaches for community detection from interaction datasets. We also introduce a new hidden Markov model for inferring community structures that vary over time. We demonstrate each of these features on three real datasets: the karate club dataset, voting data from the U.S.\ Senate (2001--2003), and temporal voting data for the U.S. Supreme Court (1990--2004).

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Exchangeable Markov processes on graphs: Feller case

The transition law of every exchangeable Feller process on the space of countable graphs is determined by a $σ$-finite measure on the space of $\{0,1\}\times\{0,1\}$-valued arrays. In discrete-time, this characterization amounts to a construction from an independent, identically distributed sequence of exchangeable random functions. In continuous-time, the behavior is enriched by a Lévy--Itô-type decomposition of the jump measure into mutually singular components that govern global, vertex-level, and edge-level dynamics. Furthermore, every such process almost surely projects to a Feller process in the space of graph limits.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Lipschitz partition processes

We introduce a family of Markov processes on set partitions with a bounded number of blocks, called Lipschitz partition processes. We construct these processes explicitly by a Poisson point process on the space of Lipschitz continuous maps on partitions. By this construction, the Markovian consistency property is readily satisfied; that is, the finite restrictions of any Lipschitz partition process comprise a compatible collection of finite state space Markov chains. We further characterize the class of exchangeable Lipschitz partition processes by a novel set-valued matrix operation.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Relatively exchangeable structures

We study random relational structures that are \emph{relatively exchangeable}---that is, whose distributions are invariant under the automorphisms of a reference structure $\mathfrak{M}$. When $\mathfrak{M}$ has {\em trivial definable closure}, every relatively exchangeable structure satisfies a general Aldous--Hoover-type representation. If $\mathfrak{M}$ satisfies the stronger properties of {\em ultrahomogeneity} and {\em $n$-disjoint amalgamation property} ($n$-DAP) for every $n\geq1$, then relatively exchangeable structures have a more precise description whereby each component depends locally on $\mathfrak{M}$.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Reversible Markov structures on divisible set partitions

We study $k$-divisible partition structures, which are families of random set partitions whose block sizes are divisible by an integer $k=1,2,\ldots$. In this setting, exchangeability corresponds to the usual invariance under relabeling by arbitrary permutations; however, for $k>1$, the ordinary deletion maps on partitions no longer preserve divisibility, and so a random deletion procedure is needed to obtain a partition structure. We describe explicit Chinese restaurant-type seating rules for generating families of exchangeable $k$-divisible partitions that are consistent under random deletion. We further introduce the notion of {\em Markovian partition structures}, which are ensembles of exchangeable Markov chains on $k$-divisible partitions that are consistent under a random process of {\em Markovian deletion}. The Markov chains we study are reversible and refine the class of Markov chains introduced in {\em J.\ Appl.\ Probab.}~{\bf48}(3):778--791.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Time-varying network models

We introduce the exchangeable rewiring process for modeling time-varying networks. The process fulfills fundamental mathematical and statistical properties and can be easily constructed from the novel operation of random rewiring. We derive basic properties of the model, including consistency under subsampling, exchangeability, and the Feller property. A reversible sub-family related to the Erdős-Rényi model arises as a special case.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

The cut-and-paste process

We characterize the class of exchangeable Feller processes evolving on partitions with boundedly many blocks. In continuous-time, the jump measure decomposes into two parts: a $σ$-finite measure on stochastic matrices and a collection of nonnegative real constants. This decomposition prompts a Lévy-Itô representation. In discrete-time, the evolution is described more simply by a product of independent, identically distributed random matrices.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Exchangeable Markov Processes on $[k]^{\zz{N}}$ with Cadlag Sample Paths

Any exchangeable Markov processes on $[k]^{\mathbb{N}}$ with cadlag sample paths projects to a Markov process on the simplex whose sample paths are cadlag and of locally bounded variation. Furthermore, any such process has a de Finetti-type description as a mixture of i.i.d. copies of time-inhomogeneous Markov processes on $[k]$. In the Feller case, these time-inhomogeneous Markov processes have a relatively simple structure; however, in the non-Feller case a greater variety of behaviors is possible since the transition law of the underlying Markov process on $[k]^{\zz{N}}$ can depend in a non-trivial way on the exchangeable $σ$-algebra of the process.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Some algebraic identities for the alpha-permanent

We show that the permanent of a matrix is a linear combination of determinants of block diagonal matrices which are simple functions of the original matrix. To prove this, we first show a more general identity involving α-permanents: for arbitrary complex numbers αand β, we show that the α-permanent of any matrix can be expressed as a linear combination of β-permanents of related matrices. Some other identities for the α-permanent of sums and products of matrices are shown, as well as a relationship between the α-permanent and general immanants. We conclude with a discussion of the computational complexity of the α-permanent and provide some numerical illustrations.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Convergence Rates of Markov Chains on Spaces of Partitions

We study the convergence rate to stationarity for a class of exchangeable partition-valued Markov chains called cut-and-paste chains. The law governing the transitions of a cut-and-paste chain are determined by products of i.i.d. stochastic matrices, which describe the chain induced on the simplex by taking asymptotic frequencies. Using this representation, we establish upper bounds for the mixing times of ergodic cut-and-paste chains, and under certain conditions on the distribution of the governing random matrices we show that the "cutoff phenomenon" holds.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

A consistent Markov partition process generated from the paintbox process

We study a family of Markov processes on $\mathcal{P}^{(k)}$, the space of partitions of the natural numbers with at most $k$ blocks. The process can be constructed from a Poisson point process on $\mathbb{R}^+\times\prod_{i=1}^k\mathcal{P}^{(k)}$ with intensity $dt\otimes\varrho_ν^{(k)}$, where $\varrho_ν$ is the distribution of the paintbox based on the probability measure $ν$ on $\masspartition$, the set of ranked-mass partitions of 1, and $\varrho_ν^{(k)}$ is the product measure on $\prod_{i=1}^k\mathcal{P}^{(k)}$. We show that these processes possess a unique stationary measure, and we discuss a particular set of reversible processes for which transition probabilities can be written down explicitly.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Ancestral branching, cut-and-paste algorithms and associated tree and partition-valued processes

We introduce an algorithm for generating a random sequence of fragmentation trees, which we call the ancestral branching algorithm. This algorithm builds on the recursive partitioning structure of a tree and gives rise to an associated family of Markovian transition kernels whose finite-dimensional transition probabilities can be written in closed-form as the product over partition-valued Markov kernels. The associated tree-valued Markov process is infinitely exchangeable provided its associated partition-valued kernel is infinitely exchangeable. We also identify a transition procedure on partitions, called the cut-and-paste algorithm, which corresponds to a previously studied partition-valued Markov process on partitions with a bounded number of blocks. Specifically, we discuss the corresponding family of tree-valued Markov kernels generated by the combination of both the ancestral branching and cut-and-paste transition probabilities and show results for the equilibrium measure of this process, as well as its associated mass fragmentation-valued and weighted tree-valued processes.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Infinitely exchangeable random graphs generated from a Poisson point process on monotone sets and applications to cluster analysis for networks

We construct an infinitely exchangeable process on the set $\cate$ of subsets of the power set of the natural numbers $\mathbb{N}$ via a Poisson point process with mean measure $Λ$ on the power set of $\mathbb{N}$. Each $E\in\cate$ has a least monotone cover in $\catf$, the collection of monotone subsets of $\cate$, and every monotone subset maps to an undirected graph $G\in\catg$, the space of undirected graphs with vertex set $\mathbb{N}$. We show a natural mapping $\cate\rightarrow\catf\rightarrow\catg$ which induces an infinitely exchangeable measure on the projective system $\catg^{\rest}$ of graphs $\catg$ under permutation and restriction mappings given an infinitely exchangeable family of measures on the projective system $\cate^{\rest}$ of subsets with permutation and restriction maps. We show potential connections of this process to applications in cluster analysis, machine learning, classification and Bayesian inference.

0 citations0 reviewsNo code linkedOpen access