Fundamental Graph Research

This research introduces novel sampling algorithms to light up unknown networks through monitors. A monitor detects its neighbors, and the edges between the monitor and its neighbors. We introduce variants of how the algorithms progress through the network based on discovered nodes' degrees and size of the network.

We compare the inference performance of our algorithm against benchmarks. Our algorithms can be tested using the Network Discovery Visualization Program (http://faculty.nps.edu/rgera/projects.html) for a live discovery of networks.

In this work we characterize the edge and node bounds for k-dense communities with k<8. The closed-form solutions presented allow bounding without running the costly graph search algorithms typically employed. By identifying the transition points between k- and (k+1)- dense communities, future researchers will be able to quickly estimate the type of communities they should find in network being investigated.