Source author record

Fangqiu Han

Fangqiu Han 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 Algorithms Databases Discrete Mathematics math.CO Neural and Evolutionary Computing physics.soc-ph Social and Information Networks

Catalog footprint

What is connected

3works

7topics

4close collaborators

Actions

Connect this record

Open graph Browse works

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.

preprint2016arXiv

Collective Decision Dynamics in Group Evacuation: Behavioral Experiment and Machine Learning Models

Identifying factors that affect human decision making and quantifying their influence remain essential and challenging tasks for the design and implementation of social and technological communication systems. We report results of a behavioral experiment involving decision making in the face of an impending natural disaster. In a controlled laboratory setting, we characterize individual and group evacuation decision making influenced by several key factors, including the likelihood of the disaster, available shelter capacity, group size, and group decision protocol. Our results show that success in individual decision making is not a strong predictor of group performance. We use an artificial neural network trained on the collective behavior of subjects to predict individual and group outcomes. Overall model accuracy increases with the inclusion of a subject-specific performance parameter based on laboratory trials that captures individual differences. In parallel, we demonstrate that the social media activity of individual subjects, specifically their Facebook use, can be used to generate an alternative individual personality profile that leads to comparable model accuracy. Quantitative characterization and prediction of collective decision making is crucial for the development of effective policies to guide the action of populations in the face of threat or uncertainty.

preprint2015arXiv

Observability of Lattice Graphs

We consider a graph observability problem: how many edge colors are needed for an unlabeled graph so that an agent, walking from node to node, can uniquely determine its location from just the observed color sequence of the walk? Specifically, let G(n,d) be an edge-colored subgraph of d-dimensional (directed or undirected) lattice of size n^d = n * n * ... * n. We say that G(n,d) is t-observable if an agent can uniquely determine its current position in the graph from the color sequence of any t-dimensional walk, where the dimension is the number of different directions spanned by the edges of the walk. A walk in an undirected lattice G(n,d) has dimension between 1 and d, but a directed walk can have dimension between 1 and 2d because of two different orientations for each axis. We derive bounds on the number of colors needed for t-observability. Our main result is that Theta(n^(d/t)) colors are both necessary and sufficient for t-observability of G(n,d), where d is considered a constant. This shows an interesting dependence of graph observability on the ratio between the dimension of the lattice and that of the walk. In particular, the number of colors for full-dimensional walks is Theta(n^(1/2)) in the directed case, and Theta(n) in the undirected case, independent of the lattice dimension. All of our results extend easily to non-square lattices: given a lattice graph of size N = n_1 * n_2 * ... * n_d, the number of colors for t-observability is Theta (N^(1/t)).

preprint2012arXiv

Memory Efficient De Bruijn Graph Construction

Massively parallel DNA sequencing technologies are revolutionizing genomics research. Billions of short reads generated at low costs can be assembled for reconstructing the whole genomes. Unfortunately, the large memory footprint of the existing de novo assembly algorithms makes it challenging to get the assembly done for higher eukaryotes like mammals. In this work, we investigate the memory issue of constructing de Bruijn graph, a core task in leading assembly algorithms, which often consumes several hundreds of gigabytes memory for large genomes. We propose a disk-based partition method, called Minimum Substring Partitioning (MSP), to complete the task using less than 10 gigabytes memory, without runtime slowdown. MSP breaks the short reads into multiple small disjoint partitions so that each partition can be loaded into memory, processed individually and later merged with others to form a de Bruijn graph. By leveraging the overlaps among the k-mers (substring of length k), MSP achieves astonishing compression ratio: The total size of partitions is reduced from $Θ(kn)$ to $Θ(n)$, where $n$ is the size of the short read database, and $k$ is the length of a $k$-mer. Experimental results show that our method can build de Bruijn graphs using a commodity computer for any large-volume sequence dataset.