Identifying Influential Nodes in Weighted, Directed Networks

Student: Kelly Fullin (Ashland University)
Mentor: Christian Fink (OWU Department of Mathematics & Computer Science)

We are creating and testing algorithms to quickly identify the most influential members of networks.  Our algorithms would be applicable to any form of network, from models of disease spread to followers on social media.  We are focusing on directed networks, such as Twitter, where connections may not be reciprocated.  By identifying the most influential members, or nodes, we can determine how best to increase or prevent spread of ideas or disease throughout a network.

In fields such as epidemiology, networks are used to visualize and predict spreading patterns of diseases.  By identifying key members (or “nodes”) of this network we might in principle stop an epidemic spread of disease by vaccinating the most influential nodes. While much research has been done in undirected networks, relatively little has focused on directed networks.  We are interested in finding a way to efficiently measure the influence of individual nodes in weighted and directed networks.  We ran computer simulations using the SIR (susceptible, infected, recovered) model of disease spread in which a single “seed” node was initially infected. We then defined this node’s influence by counting the total number of nodes it infected.  We have succeeded in developing an algorithm that initial tests indicate accurately determines the influence of each node up to 10 times faster than actually running the brute force simulations.