BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Blair D. Sullivan

Blair D. Sullivan appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Data Structures and Algorithmsmath.COSocial and Information NetworksComputational Complexityquant-phApplicationsMachine Learningmath.NTphysics.soc-ph

Catalog footprint

What is connected

15works
9topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

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.

Published work

15 published item(s)

preprint2024arXiv

Overlapping and Robust Edge-Colored Clustering in Hypergraphs

A recent trend in data mining has explored (hyper)graph clustering algorithms for data with categorical relationship types. Such algorithms have applications in the analysis of social, co-authorship, and protein interaction networks, to name a few. Many such applications naturally have some overlap between clusters, a nuance which is missing from current combinatorial models. Additionally, existing models lack a mechanism for handling noise in datasets. We address these concerns by generalizing Edge-Colored Clustering, a recent framework for categorical clustering of hypergraphs. Our generalizations allow for a budgeted number of either (a) overlapping cluster assignments or (b) node deletions. For each new model we present a greedy algorithm which approximately minimizes an edge mistake objective, as well as bicriteria approximations where the second approximation factor is on the budget. Additionally, we address the parameterized complexity of each problem, providing FPT algorithms and hardness results.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

A color-avoiding approach to subgraph counting in bounded expansion classes

We present an algorithm to count the number of occurrences of a pattern graph $H$ as an induced subgraph in a host graph $G$. If $G$ belongs to a bounded expansion class, the algorithm runs in linear time. Our design choices are motivated by the need for an approach that can be engineered into a practical implementation for sparse host graphs. Specifically, we introduce a decomposition of the pattern $H$ called a counting dag $\vec C(H)$ which encodes an order-aware, inclusion-exclusion counting method for $H$. Given such a counting dag and a suitable linear ordering $\mathbb G$ of $G$ as input, our algorithm can count the number of times $H$ appears as an induced subgraph in $G$ in time $O(\|\vec C\| \cdot h \text{wcol}_{h}(\mathbb G)^{h-1} |G|)$, where $\text{wcol}_h(\mathbb G)$ denotes the maximum size of the weakly $h$-reachable sets in $\mathbb G$. This implies, combined with previous results, an algorithm with running time $O(4^{h^2}h (\text{wcol}_h(G)+1)^{h^3} |G|)$ which only takes $H$ and $G$ as input. We note that with a small modification, our algorithm can instead use strongly $h$-reachable sets with running time $O(\|\vec C\| \cdot h \text{col}_{h}(\mathbb G)^{h-1} |G|)$, resulting in an overall complexity of $O(4^{h^2}h \text{col}_h(G)^{h^2} |G|)$ when only given $H$ and $G$. Because orderings with small weakly/strongly reachable sets can be computed relatively efficiently in practice [11], our algorithm provides a promising alternative to algorithms using the traditional $p$-treedepth colouring framework [13]. We describe preliminary experimental results from an initial open source implementation which highlight its potential.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

A Fast Parameterized Algorithm for Co-Path Set

The k-CO-PATH SET problem asks, given a graph G and a positive integer k, whether one can delete k edges from G so that the remainder is a collection of disjoint paths. We give a linear-time fpt algorithm with complexity O^*(1.588^k) for deciding k-CO-PATH SET, significantly improving the previously best known O^*(2.17^k) of Feng, Zhou, and Wang (2015). Our main tool is a new O^*(4^{tw(G)}) algorithm for CO-PATH SET using the Cut&Count framework, where tw(G) denotes treewidth. In general graphs, we combine this with a branching algorithm which refines a 6k-kernel into reduced instances, which we prove have bounded treewidth.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Asymptotic Analysis of Equivalences and Core-Structures in Kronecker-Style Graph Models

Growing interest in modeling large, complex networks has spurred significant research into generative graph models. Kronecker-style models (SKG and R-MAT) are often used due to their scalability and ability to mimic key properties of real-world networks. Although a few papers theoretically establish these models' behavior for specific parameters, many claims used to justify their use are supported only empirically. In this work, we prove several results using asymptotic analysis which illustrate that empirical studies may not fully capture the true behavior of the models. Paramount to the widespread adoption of Kronecker-style models was the introduction of a linear-time edge-sampling variant (R-MAT), which existing literature typically treats as interchangeable with SKG. We prove that although several R-MAT formulations are asymptotically equivalent, their behavior diverges from that of SKG. Further, we show these results are observable even at relatively small graph sizes. Second, we consider a case where asymptotic analysis reveals unexpected behavior within a given model.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Tree decompositions and social graphs

Recent work has established that large informatics graphs such as social and information networks have non-trivial tree-like structure when viewed at moderate size scales. Here, we present results from the first detailed empirical evaluation of the use of tree decomposition (TD) heuristics for structure identification and extraction in social graphs. Although TDs have historically been used in structural graph theory and scientific computing, we show that---even with existing TD heuristics developed for those very different areas---TD methods can identify interesting structure in a wide range of realistic informatics graphs. Our main contributions are the following: we show that TD methods can identify structures that correlate strongly with the core-periphery structure of realistic networks, even when using simple greedy heuristics; we show that the peripheral bags of these TDs correlate well with low-conductance communities (when they exist) found using local spectral computations; and we show that several types of large-scale "ground-truth" communities, defined by demographic metadata on the nodes of the network, are well-localized in the large-scale and/or peripheral structures of the TDs. Our other main contributions are the following: we provide detailed empirical results for TD heuristics on toy and synthetic networks to establish a baseline to understand better the behavior of the heuristics on more complex real-world networks; and we prove a theorem providing formal justification for the intuition that the only two impediments to low-distortion hyperbolic embedding are high tree-width and long geodesic cycles. Our results suggest future directions for improved TD heuristics that are more appropriate for realistic social graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Multi-Level Anomaly Detection on Time-Varying Graph Data

This work presents a novel modeling and analysis framework for graph sequences which addresses the challenge of detecting and contextualizing anomalies in labelled, streaming graph data. We introduce a generalization of the BTER model of Seshadhri et al. by adding flexibility to community structure, and use this model to perform multi-scale graph anomaly detection. Specifically, probability models describing coarse subgraphs are built by aggregating probabilities at finer levels, and these closely related hierarchical models simultaneously detect deviations from expectation. This technique provides insight into a graph's structure and internal context that may shed light on a detected event. Additionally, this multi-scale analysis facilitates intuitive visualizations by allowing users to narrow focus from an anomalous graph to particular subgraphs or nodes causing the anomaly. For evaluation, two hierarchical anomaly detectors are tested against a baseline Gaussian method on a series of sampled graphs. We demonstrate that our graph statistics-based approach outperforms both a distribution-based detector and the baseline in a labeled setting with community structure, and it accurately detects anomalies in synthetic and real-world datasets at the node, subgraph, and graph levels. To illustrate the accessibility of information made possible via this technique, the anomaly detector and an associated interactive visualization tool are tested on NCAA football data, where teams and conferences that moved within the league are identified with perfect recall, and precision greater than 0.786.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

On the Threshold of Intractability

We study the computational complexity of the graph modification problems Threshold Editing and Chain Editing, adding and deleting as few edges as possible to transform the input into a threshold (or chain) graph. In this article, we show that both problems are NP-complete, resolving a conjecture by Natanzon, Shamir, and Sharan (Discrete Applied Mathematics, 113(1):109--128, 2001). On the positive side, we show the problem admits a quadratic vertex kernel. Furthermore, we give a subexponential time parameterized algorithm solving Threshold Editing in $2^{O(\surd k \log k)} + \text{poly}(n)$ time, making it one of relatively few natural problems in this complexity class on general graphs. These results are of broader interest to the field of social network analysis, where recent work of Brandes (ISAAC, 2014) posits that the minimum edit distance to a threshold graph gives a good measure of consistency for node centralities. Finally, we show that all our positive results extend to the related problem of Chain Editing, as well as the completion and deletion variants of both problems.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

An Integrated Programming and Development Environment for Adiabatic Quantum Optimization

Adiabatic quantum computing is a promising route to the computational power afforded by quantum information processing. The recent availability of adiabatic hardware has raised challenging questions about how to evaluate adiabatic quantum optimization programs. Processor behavior depends on multiple steps to synthesize an adiabatic quantum program, which are each highly tunable. We present an integrated programming and development environment for adiabatic quantum optimization called JADE that provides control over all the steps taken during program synthesis. JADE captures the workflow needed to rigorously specify the adiabatic quantum optimization algorithm while allowing a variety of problem types, programming techniques, and processor configurations. We have also integrated JADE with a quantum simulation engine that enables program profiling using numerical calculation. The computational engine supports plug-ins for simulation methodologies tailored to various metrics and computing resources. We present the design, integration, and deployment of JADE and discuss its potential use for benchmarking adiabatic quantum optimization programs by the quantum computer science community.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Locally Estimating Core Numbers

Graphs are a powerful way to model interactions and relationships in data from a wide variety of application domains. In this setting, entities represented by vertices at the "center" of the graph are often more important than those associated with vertices on the "fringes". For example, central nodes tend to be more critical in the spread of information or disease and play an important role in clustering/community formation. Identifying such "core" vertices has recently received additional attention in the context of {\em network experiments}, which analyze the response when a random subset of vertices are exposed to a treatment (e.g. inoculation, free product samples, etc). Specifically, the likelihood of having many central vertices in any exposure subset can have a significant impact on the experiment. We focus on using $k$-cores and core numbers to measure the extent to which a vertex is central in a graph. Existing algorithms for computing the core number of a vertex require the entire graph as input, an unrealistic scenario in many real world applications. Moreover, in the context of network experiments, the subgraph induced by the treated vertices is only known in a probabilistic sense. We introduce a new method for estimating the core number based only on the properties of the graph within a region of radius $δ$ around the vertex, and prove an asymptotic error bound of our estimator on random graphs. Further, we empirically validate the accuracy of our estimator for small values of $δ$ on a representative corpus of real data sets. Finally, we evaluate the impact of improved local estimation on an open problem in network experimentation posed by Ugander et al.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Zig-Zag Numberlink is NP-Complete

When can $t$ terminal pairs in an $m \times n$ grid be connected by $t$ vertex-disjoint paths that cover all vertices of the grid? We prove that this problem is NP-complete. Our hardness result can be compared to two previous NP-hardness proofs: Lynch's 1975 proof without the ``cover all vertices'' constraint, and Kotsuma and Takenaga's 2010 proof when the paths are restricted to have the fewest possible corners within their homotopy class. The latter restriction is a common form of the famous Nikoli puzzle \emph{Numberlink}; our problem is another common form of Numberlink, sometimes called \emph{Zig-Zag Numberlink} and popularized by the smartphone app \emph{Flow Free}.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Adiabatic Quantum Programming: Minor Embedding With Hard Faults

Adiabatic quantum programming defines the time-dependent mapping of a quantum algorithm into an underlying hardware or logical fabric. An essential step is embedding problem-specific information into the quantum logical fabric. We present algorithms for embedding arbitrary instances of the adiabatic quantum optimization algorithm into a square lattice of specialized unit cells. These methods extend with fabric growth while scaling linearly in time and quadratically in footprint. We also provide methods for handling hard faults in the logical fabric without invoking approximations to the original problem, and illustrate their versatility through numerical studies of embeddabilty versus fault rates in square lattices of complete bipartite unit cells. The studies show these algorithms are more resilient to faulty fabrics than naive embedding approaches, a feature which should prove useful in benchmarking the adiabatic quantum optimization algorithm on existing faulty hardware.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Counting paths in digraphs

Say a digraph is k-free if it has no directed cycles of length at most k, for positive integers k. Thomasse conjectured that the number of induced 3-vertex directed paths in a simple 2-free digraph on n vertices is at most (n-1)n(n+1)/15. We present an unpublished result of Bondy proving that there are at most 2n^3/25 such paths, and prove that for the class of circular interval digraphs, an upper bound of n^3/16 holds. We also study the problem of bounding the number of (non-induced) 4-vertex paths in 3-free digraphs. We show an upper bound of 4n^4/75 using Bondy's result for Thomasse's conjecture.

0 citations0 reviewsNo code linkedOpen access
preprint2007arXiv

Cycles in dense digraphs

Let G be a digraph (without parallel edges) such that every directed cycle has length at least four; let $β(G)$ denote the size of the smallest subset X in E(G) such that $G\X$ has no directed cycles, and let $γ(G)$ be the number of unordered pairs {u,v} of vertices such that u,v are nonadjacent in G. It is easy to see that if $γ(G) = 0$ then $β(G) = 0$; what can we say about $β(G)$ if $γ(G)$ is bounded? We prove that in general $β(G)$ is at most $γ(G)$. We conjecture that in fact $β(G)$ is at most $γ(G)/2$ (this would be best possible if true), and prove this conjecture in two special cases: 1. when V(G) is the union of two cliques, 2. when the vertices of G can be arranged in a circle such that if distinct u,v,w are in clockwise order and uw is a (directed) edge, then so are both uv and vw.

0 citations0 reviewsNo code linkedOpen access
preprint2007arXiv

Heights in finite projective space, and a problem on directed graphs

Let $\F_p = \Z/p\Z$. The \emph{height} of a point $\mathbf{a}=(a_1,..., a_d) \in \F_p^d$ is $h_p(\mathbf{a}) = \min \left\{\sum_{i=1}^d (ka_i \mod p) : k=1,...,p-1\right\}.$ Explicit formulas and estimates are obtained for the values of the height function in the case $d=2,$ and these results are applied to the problem of determining the minimum number of edges the must be deleted from a finite directed graph so that the resulting subgraph is acyclic.

0 citations0 reviewsNo code linkedOpen access