Research Projects

Research Projects

Research projects are incorporated into MA 4404, or as part of the thesis for the students getting their masters in Applied Mathematics with concentration in Network Science.

Comparing Network Using The Distance k Matrix: Extending the Descriptive Power of the Degree Sequence to Multiple Dimensions, sponsored by DoD

LTC Jon Roginski is studying the importance of understanding graph structure in a world characterized by connectivity. Matrices such as the adjacency, distance, reciprocal distance, walk, and LaPlacian offer a well-studied, compact structure to represent graph information. Two of these matrix representations that form the foundation of his work are the adjacency matrix and the distance matrix. The adjacency matrix depicts the first order relationship enumerating which vertices are connected to which other vertices. The distance matrix shows more information, namely the length of shortest paths between vertex pairs. The adjacency matrix may be summarized by the degree sequence, a list of the adjacency matrix row sums. We introduce and explore the distance-k neighborhood matrix (more simply, k-matrix), a new matrix that extends the degree sequence to capture the distribution of each distance in a graph from 1 to k, where k is the graph diameter. It is to the distance matrix what the degree sequence is to the adjacency matrix. The k-matrix may be calculated using the adjacency and boolean matrices, or computed algorithmically in O(n) time, as it is an aggregation of all-pairs shortest paths. We use combinatorics techniques to show the k-matrix to include many of the statistics and topological characteristics currently used to describe graphs and networks.

Constructing Information Networks from Secondary Storage with Bulk Analysis Tools, sponsored by the Defense Intelligence Agency (under the supervision of Michael McCarrin and Ralucca Gera)

CPT Janina Green is looking at establishing if email proximity and quantity of email address pairs on a digital storage device are a good indication of network connections. This theory will be tested using bulkextractor, a digital forensic tool, to extract data that resembles email addresses from disk images, and record their location on the disk image. The data will be used to construct the social network of user(s) of the computer.

Price Analysis on DLA Contracts, sponsored by Defense Logistics Agency

Janie Maddox and Ralucca Gera will be looking at reviewing service contract files and conduct interviews to determine the appropriateness of current pricing memos and the proper use of price/cost analysis and pricing memos to improve acquisition pricing payoffs, and to evaluate requirements and IGCE creators regarding their training, validity of the IGCEs, and contracting officer’s/specialist’s interpretation/use of the IGCE We will evaluate DLA’s Determining Fair and Reasonableness Using Price or Cost Analysis Methods training course for appropriate content Evaluate the course content for adequate guidance and training applicable to price analysis and price reasonableness determinations in accordance with FAR/DFAR/DLAD requirements.

Lighting up networks through inference, sponsored by DoD

Nick Juliano and Erin Moore studied the discovery of networks through inference. There are various types of networks and each one has its own properties that sets it aside from the others. Thus a general framework that works for all types of networks will not produce reliable results. The framework in question here is the inference of large unknown networks encountered in the real world, for which the real network is not known generally because it is extremely large or because complete information about it cannot be captured. Thus, researchers and operators usually work with an inferred network of this true network, whose information is incomplete. The degree of incompleteness of information is generally unknown as well, since the true network is unknown and no standard techniques exist to measure their difference. They introduced and tested multiple algorithms to assess which algorithms perform better on specific type of networks. A visualization of the network discovery can be found here.

Sequential Centrality-based Monitor Placement on Networks, sponsored by DoD

James Carbaugh, Matt Fletcher, Woei Lee and Russ Nelson worked on monitoring knowing networks. Understanding and particularly measuring a network's structure is a complex problem, and there is no general reliable way of measuring the structure in order to compare networks. In this research we present heuristics for sequential monitor placement to infer the edges of a given network. In particular we look for the minimum number of monitors that could detect 90% of a networks edges. The monitors were placed according to four different centralities, which identify the most important nodes in a network to verify the hypothesis that using these important nodes will provide more accurate knowledge of the relationships in the network. We introduce an algorithm to place those monitors according to betweenness, closeness, degree and a new centrality called 2-hop centrality.

The Marginal Benefit of Monitor Placement on Networks, sponsored by DoD

Ben Davis, Bing Lim, Gary Lazzro and Erik Rye worked on inferring the structure of an unknown network, a difficult problem of interest to researchers, academics, and industry. They developed a novel algorithm to infer nodes and edges in an unknown network. The algorithm utilizes sensors that have the capability to detect and label nodes, edges incident to the node and neighboring nodes. The algorithm places new sensors at the highest degree neighboring node that have been inferred, and it will stop when attempting to place a sensor at a node where a sensor already exists. The algorithm has an adjustable restarting feature which varies between restarting at a previously discovered but unmonitored node and a random teleportation to an unexplored node somewhere in the network. They compared the inference performance of the new algorithm against inference through random walks and random placement in four distinct network - a Barabasi-Albert network, an Erdos-Renyi random network, and two data sets from the Stanford Large Network Dataset Collection. The new algorithm outperforms random walk inference in node discovery in all test cases, and outperforms random walk in edge inference in three of the four test networks. A visualization of the network discovery can be found here.

Internet Topology, sponsored by Department of Homeland Security (under the supervision of Rob Beverly and Ralucca Gera)

Daryl Lee worked on understanding the Internet's dynamics using large-graph comparison measures. When applied on specific portions of the Internet, these measures identified Internet connectivity changes in Egypt and Libya during the Arab Spring. These measures were also applied to a large university network, where comparisons between ground-truth and probe-discovered topologies were performed. Daryl is currently a System Consultant with Singapore Technologies Electronics, with a focus on Big Data technologies.

Daryl received the Masters of Science (Applied Mathematics) from Naval Postgraduate School (NPS) and Master of Science (Defense Technology and Systems) from National University of Singapore (NUS).

Jamar Wright worked on a temporal comparison of the Internet by examining whether the time of the day is a factor when measuring Internet topology.

Jamar is now an instructor at the United States Military Academy.

Brit Landry compared Internet probing methodologies through an analysis of large dynamical graphs.  Brit explored CAIDA's and NPS's probing methodologies to verify that NPS's probing methodology discovers comparable Internet topology to CAIDA's but in less time. 

Brit is now an instructor at the United States Military Academy.

Erik Rye also worked on measuring the Internet by creating Internet like topologies. The Internet measurement community is beset by a lack of “ground truth,” or knowledge of the real, underlying network in topology inference experiments. While better tools and methodologies can be developed, quantifying the effectiveness of these mapping utilities and explaining pathologies is difficult, if not impossible, without knowing the network topology being probed. In this thesis we present a tool that eliminates topological uncertainty in an emulated, virtualized environment. First, we automatically build topological ground truth according to various network generation models and create emulated Cisco router networks by leveraging and modifying existing emulation software. We then automate topological inference from one vantage point at a time for every vantage point in the network. Finally, we incorporate a mechanism to study common sources of network topology inference abnormalities by including the ability to induce link failures within the network. In addition, this thesis reexamines previous work in sampling Autonomous System-level Internet graphs to procure realistic models for emulation and simulation. We build upon this work by including additional data sets, and more recent Internet topologies to sample from, and observe divergent results from the authors of the original work. Lastly, we introduce a new technique for sampling Internet graphs that better retains particular graph metrics across multiple timeframes and data sets.

Erik is now an instructor at the United States Naval Academy.

View All

Page Contents

Quick Links

  • NetSci Logo