You are here

Invited Paper Session Abstracts - Bridging Network Science and Graph Theory

Thursday, August 2, 1:30 p.m. - 4:20 p.m., Grand Ballroom II, Tower Building

The current session aims at bringing together researchers from different areas to learn or apply their knowledge to network science. While the foundations of Network science are in graph theory, the discipline evolved to include sociologists, computer scientist and others that are interested in understanding and analyzing social networks, technological network, biological networks and networks of information. The network science field bloomed as big data emerged, yet mathematicians are a minority at these conferences. The types of contributions for this session are either state-of-the art overviews of network science research topics, or newly developed theory/applications in network science that is of interest to the mathematical community.

Ralucca Gera, Naval Postgraduate School
Karl Schmitt, Valparaiso University

(NEW!) Using Machine Learning to Classify and Characterize Networks

1:30 p.m. - 1:50 p.m.
Karl Schmitt, Valparaiso University

Teaching Graph Theory and Network Science (CANCELED)

1:30 p.m. -1:50 p.m.
Ralucca Gera, Naval Postgraduate School

We illustrate how the Naval Postgraduate School’s math department augmented the teaching of graph theory by adding a network science course. We present an overview of some classical topics in graph theory, and their transition and extension in the network science world. We indicate some early examples that motivate the study of network science by demonstrating a range of applications that can be analyzed with network concepts and tools.

(NEW!) Seeing Red: Locating People of Interest in Dark Networks

2:00 p.m. - 2:20 p.m.

Pivithuru Wijegunawardana

Teaching Network Science at Different Academic Levels (CANCELED)

2:00 p.m. - 2:20 p.m.
Jon Roginski, United States Military Academy

Productive learning environments strike a balance between student motivation and the necessary learning outcomes associated with a particular course. We explore ways to achieve such a balance and discusses some of the subtle benefits that spring from that balance. We present course designs that foster student motivation and encourages independent learning, where students began to see coursework, concepts, and feedback as productive and globally meaningful rather than corrective and locally meaningful. We overview teaching network science to undergraduates, graduate students, short courses and elementary school teachers.

Guessing Numbers of Graphs

2:30 p.m. - 2:50 p.m.
Puck Rombach, University of Vermont

The guessing number problem is the following. What is the largest family of colorings of a graph such that the color of each vertex is determined by its neighborhood? This problem is equivalent to finding protocols for network coding. I will discuss results on general graphs, and recent asymptotic results for odd cycles, which is joint work with Ross Atkins and Fiona Skerman.

Tropical Principal Component Analysis and its Application to Phylogenetics

3:00 p.m. - 3:20 p.m.
Ruriko Yoshida, Naval Postgraduate School

Principal component analysis is a widely-used method for the dimensionality reduction of a given data set in a high-dimensional Euclidean space. Here we define and analyze two analogues of principal component analysis in the setting of tropical geometry. In one approach, we study the Stiefel tropical linear space of fixed dimension closest to the data points in the tropical projective torus; in the other approach, we consider the tropical polytope with a fixed number of vertices closest to the data points. We then give approximate algorithms for both approaches and apply them to phylogenetics, testing the methods on simulated phylogenetic data and on an empirical dataset of Apicomplexa genomes. This is joint work with Lean Zhang UC Berkeley and Xu Zhang at u of Kentucky.

Using Machine Learning to Classify and Characterize Networks

3:30 p.m. - 3:50 p.m.
Karl Schmitt, Valparaiso University

Networks are often labeled according to the underlying phenomena that they represent, such as re-tweets, protein interactions, or web page links. This research seeks to use machine learning techniques to gain a better understanding of the categories of networks on the Network Repository ( and then classify unlabeled networks into categories that make sense. It is generally believed that networks from different categories have inherently unique network characteristics. This research provides conclusive evidence to validate this belief by presenting the results of global network clustering and classification into common categories using machine learning algorithms. The machine learning techniques of Decisions Trees, Random Forests, Linear Support Vector Classification and Gaussian Naive Bayes were applied to a 14-feature “identifying vector” for each graph. During cross-validation, the best technique, Gaussian Naive Bayes, achieved an accuracy of 92.8%. After training the machine learning algorithm it was applied to a collection of initially unlabeled graphs from the Network Repository. Results were then manually checked by determining (when possible) original sources for these graphs. Finally, we examined the accuracy of our results and discussed how future researchers can make use of this process. This is joint work with Ryan Rossi (Adobe Research), Nesreen Ahmed (Intel Labs), Sucheta Soundarajan (Syracuse University), James Canning (SUNY Geneseo), Emma Ingram (University of Alabama), Adriana Ortiz (University of Puerto Rico), and Sammantha Nowak-Wolff (Valparaiso University).

Seeing Red: Locating People of Interest in Dark Networks

4:00 p.m. - 4:20 p.m.
Pivithuru Wijegunawardana

Dark networks, which describe networks with covert entities and connections such as those representing illegal activities, are of great interest to intelligence analysts. However, before studying such a network, one must first collect appropriate network data. Collecting accurate network data in such a setting is a challenging task, as data collectors will make inferences, which may be incorrect, based on available intelligence data, which may itself be misleading. In our work, we consider the problem of how to effectively sample dark networks, in which sampling queries may return incorrect information, with the specific goal of locating people of interest. We present RedLearn and RedLearnRS, two algorithms for crawling dark networks with the goal of maximizing the identification of nodes of interest, given a limited sampling budget. RedLearn assumes that a query on a node can accurately return whether a node represents a person of interest, while RedLearnRS dispenses with that assumption. We consider realistic error scenarios, which describe how individuals in a dark network may attempt to conceal their connections. We evaluate the performance of the algorithms on several real-world networks, including dark networks, as well as various synthetic dark network structures proposed in the criminology literature. Our analysis shows that RedLearn and RedLearnRS meet or outperform other sampling algorithms. This is joint work with Vatsal Ojha, Ralucca Gera, and Sucheta Soundarajan.