### Core team:

# Puck Rombach

### University of Vermont

### Department of Mathematics and Statistics, Assistant Professor

Rombach's research bridges gaps between the pure and applied sides of graph/network theory. Sample areas of interest for Rombach include graph coloring, random graphs, algorithms and complexity, graph representations of matroids, crime network modeling, and core-periphery/centrality detection in networks. Prior to UVM, Rombach was an assistant adjunct professor at UCLA, working with Andrea Bertozzi. Rombach earned her PhD at the University of Oxford in 2013, under the supervision of Mason Porter and Alex Scott.

#### Most recent papers:

Role colouring graphs in hereditary classes.

Puck Rombach, Christopher Purcell. Preprint, 2018.[pdf]

**Abstract:**

We study the computational complexity of computing role colourings of graphs in hereditary classes. We are interested in describing the family of hereditary classes on which a role colouring with k colours can be computed in polynomial time. In particular, we wish to describe the boundary between the “hard” and “easy” classes. The notion of a boundary class has been introduced by Alekseev in order to study such boundaries. Our main results are a boundary class for the k-role colouring problem and the related k-coupon colouring problem which has recently received a lot of attention in the literature. The latter result makes use of a technique for generating regular graphs of arbitrary girth which may be of independent interest.

Rank Aggregation for Course Sequence Discovery.

Mihai Cucuringu, Charles Z. Marshak, Dillon Montag, Puck Rombach. Studies in Computational Intelligence, , , 2017.[pdf] [journal page] [arXiv]

**Abstract:**

This work extends the rank aggregation framework for the setting of discovering optimal course sequences at the university level, and contributes to the literature on educational applications of network analysis. Each student provides a partial ranking of the courses taken throughout her or his undergraduate career. We build a network of courses by computing pairwise rank comparisons between courses based on the order students typically take them, and aggregate the results over the entire student population, to obtain a proxy for the rank offset between pairs of courses. We extract a global ranking of the courses via several state-of-the art algorithms for ranking with pairwise noisy information, including SerialRank, Rank Centrality, and the recent SyncRank based on the group synchronization problem. We test this application of rank aggregation on 15 years of student data from the Department of Mathematics at the University of California, Los Angeles (UCLA). Furthermore, we experiment with the above approach on different subsets of the student population conditioned on final GPA, and highlight several differences in the obtained rankings that uncover potential hidden pre-requisites in the Mathematics curriculum.

Core-Periphery Structure in Networks (Revisited).

Puck Rombach, Mason A. Porter, James H. Fowler, Peter J. Mucha. SIAM Rev., 619-649, 59, 2017.[pdf]

**Abstract:**

Intermediate-scale (or “meso-scale'') structures in networks have received considerable attention, as the algorithmic detection of such structures makes it possible to discover network features that are not apparent either at the local scale of nodes and edges or at the global scale of summary statistics. Numerous types of meso-scale structures can occur in networks, but investigations of such features have focused predominantly on the identification and study of community structure. In this paper, we develop a new method to investigate the meso-scale feature known as core-periphery structure, which entails identifying densely connected core nodes and sparsely connected peripheral nodes. In contrast to communities, the nodes in a core are also reasonably well-connected to those in a network's periphery. Our new method of computing core-periphery structure can identify multiple cores in a network and takes into account different possible core structures. We illustrate the differences between our method and several existing methods for identifying which nodes belong to a core, and we use our technique to examine core-periphery structure in examples of friendship, collaboration, transportation, and voting networks. For this new SIGEST version of our paper, we also discuss our work's relevance in the context of recent developments in the study of core-periphery structure.

Detection of core–periphery structure in networks using spectral methods and geodesic paths.

Puck Rombach, Mason A. Porter, Mihai Cucuringu, Sang Hoon Lee. European Journal of Applied Mathematics, , 27, 2016.[pdf]

**Abstract:**

We introduce several novel and computationally efficient methods for detecting "core--periphery structure" in networks. Core--periphery structure is a type of mesoscale structure that includes densely-connected core vertices and sparsely-connected peripheral vertices. Core vertices tend to be well-connected both among themselves and to peripheral vertices, which tend not to be well-connected to other vertices. Our first method, which is based on transportation in networks, aggregates information from many geodesic paths in a network and yields a score for each vertex that reflects the likelihood that a vertex is a core vertex. Our second method is based on a low-rank approximation of a network's adjacency matrix, which can often be expressed as a tensor-product matrix. Our third approach uses the bottom eigenvector of the random-walk Laplacian to infer a coreness score and a classification into core and peripheral vertices. We also design an objective function to (1) help classify vertices into core or peripheral vertices and (2) provide a goodness-of-fit criterion for classifications into core versus peripheral vertices. To examine the performance of our methods, we apply our algorithms to both synthetically-generated networks and a variety of networks constructed from real-world data sets.

Growth and containment of a hierarchical criminal network.

Puck Rombach, Charles Z. Marshak, Andrea L. Bertozzi, Maria R. D'Orsogna. Physical Review, e93, 93, 2016.[pdf]

**Abstract:**

We model the hierarchical evolution of an organized criminal network via antagonistic recruitment and pursuit processes. Within the recruitment phase, a criminal kingpin enlists new members into the network, who in turn seek out other affiliates. New recruits are linked to established criminals according to a probability distribution that depends on the current network structure. At the same time, law enforcement agents attempt to dismantle the growing organization using pursuit strategies that initiate on the lower level nodes and that unfold as self-avoiding random walks. The global details of the organization are unknown to law enforcement, who must explore the hierarchy node by node. We halt the pursuit when certain local criteria of the network are uncovered, encoding if and when an arrest is made; the criminal network is assumed to be eradicated if the kingpin is arrested. We first analyze recruitment and study the large scale properties of the growing network; later we add pursuit and use numerical simulations to study the eradication probability in the case of three pursuit strategies, the time to first eradication, and related costs. Within the context of this model, we find that eradication becomes increasingly costly as the network increases in size and that the optimal way of arresting the kingpin is to intervene at the early stages of network formation. We discuss our results in the context of dark network disruption and their implications on possible law enforcement strategies.

Pursuit on an organized crime network.

Charles Z. Marshak, Puck Rombach, Andrea L. Bertozzi, Maria R. D'Orsogna. Physical Review E, , 93, 2016.[pdf] [journal page]

**Abstract:**

We model the hierarchical evolution of an organized criminal network via antagonistic recruitment and pursuit processes. Within the recruitment phase, a criminal kingpin enlists new members into the network, who in turn seek out other affiliates. New recruits are linked to established criminals according to a probability distribution that depends on the current network structure. At the same time, law enforcement agents attempt to dismantle the growing organization using pursuit strategies that initiate on the lower level nodes and that unfold as self-avoiding random walks. The global details of the organization are unknown to law enforcement, who must explore the hierarchy node by node. We halt the pursuit when certain local criteria of the network are uncovered, encoding if and when an arrest is made; the criminal network is assumed to be eradicated if the kingpin is arrested. We first analyze recruitment and study the large scale properties of the growing network; later we add pursuit and use numerical simulations to study the eradication probability in the case of three pursuit strategies, the time to first eradication, and related costs. Within the context of this model, we find that eradication becomes increasingly costly as the network increases in size and that the optimal way of arresting the kingpin is to intervene at the early stages of network formation. We discuss our results in the context of dark network disruption and their implications on possible law enforcement strategies.

**Abstract:**

For a given number of colours, s, the guessing number of a graph is the base s logarithm of the size of the largest family of colourings of the vertex set of the graph such that the colour of each vertex can be determined from the colours of the vertices in its neighbourhood. An upper bound for the guessing number of the n-vertex cycle graph Cn is n/2. It is known that the guessing number equals n/2 whenever n is even or s is a perfect square [7]. We show that, for any given integer s ≥ 2, if a is the largest factor of s less than or equal to √s, for suﬃciently large odd n, the guessing number of Cn with s colours is (n−1)/2+logs(a). This answers a question posed by Christoﬁdes and Markstr¨om in 2011 [7]. We also present an explicit protocol which achieves this bound for every n. Linking this to index coding with side information, we deduce that the information defect of Cn with s colours is (n+1)/2−logs(a) for suﬃciently large odd n. Our results are a generalisation of the s = 2 case which was proven in [3].

On the complexity of role colouring planar graphs, trees and cographs.

Christopher Purcell, Puck Rombach. Journal of Discrete Algorithms, 1-8, 35, 2015.[pdf] [journal page]

**Abstract:**

We prove several results about the complexity of the role colouring problem. A role colouring of a graph G is an assignment of colours to the vertices of G such that two vertices of the same colour have identical sets of colours in their neighbourhoods. We show that the problem of finding a role colouring with 1 < k < n colours is NP-hard for planar graphs. We show that restricting the problem to trees yields a polynomially solvable case, as long as k is either constant or has a constant difference with n, the number of vertices in the tree. Finally, we prove that cographs are always k-role-colourable for 1 < k <= n and construct such a colouring in polynomial time.

An Independent Process Approximation to Sparse Random Graphs with a Prescribed Number of Edges and Triangles.

Stephan DeSalvo, Puck Rombach. Preprint, 2015.[pdf] [arXiv]

**Abstract:**

We prove a pre-asymptotic bound on the total variation distance between the uniform distribution over two types of undirected graphs with n nodes. One distribution places a prescribed number of kT triangles and kS edges not involved in a triangle independently and uniformly over all possibilities, and the other is the uniform distribution over simple graphs with exactly kT triangles and kS edges not involved in a triangle. As a corollary, for kS=o(n) and kT=o(n) as n tends to infinity, the total variation distance tends to 0, at a rate that is given explicitly. Our main tool is Chen-Stein Poisson approximation, hence our bounds are explicit for all finite values of the parameters.

Task-Based Core-Periphery Organization of Human Brain Dynamics.

Danielle Bassett, Nicholas Wymbs, Puck Rombach, et al.. PLoS Computational Biology, , 9, 2013.[pdf] [journal page]

**Abstract:**

As a person learns a new skill, distinct synapses, brain regions, and circuits change over time. In this paper, we develop methods to examine patterns of correlated activity across a large set of brain regions. We use our core-periphery detection method, together with time-dependent community structure to find that dynamically stiff regions correspond to the core, and the flexible regions to the periphery. Surprisingly, the way these regions organise is also linked to how fast the human subjects learn a new task.

Discriminating Power of Centrality Measures.

Puck Rombach, Mason A. Porter. Preprint, 2013.[pdf] [journal page]

**Abstract:**

The calculation of centrality measures is common practice in the study of networks, as they attempt to quantify the importance of individual vertices, edges, or other components. In this paper, we examine a conjecture posed by E. Estrada regarding the ability of several measures to distinguish the vertices of networks.

(show all)