Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to nonfederal websites. Their policies may differ from this site.

Abstract We consider the simultaneous propagation of two contagions over a social network. We assume a threshold model for the propagation of the two contagions and use the formal framework of discrete dynamical systems. In particular, we study an optimization problem where the goal is to minimize the total number of new infections subject to a budget constraint on the total number of available vaccinations for the contagions. While this problem has been considered in the literature for a single contagion, our work considers the simultaneous propagation of two contagions. This optimization problem is NPhard. We present two main solution approaches for the problem, namely an integer linear programming (ILP) formulation to obtain optimal solutions and a heuristic based on a generalization of the set cover problem. We carry out a comprehensive experimental evaluation of our solution approaches using many realworld networks. The experimental results show that our heuristic algorithm produces solutions that are close to the optimal solution and runs several orders of magnitude faster than the ILPbased approach for obtaining optimal solutions. We also carry out sensitivity studies of our heuristic algorithm.more » « less

We consider the simultaneous propagation of two contagions over a social network. We assume a threshold model for the propagation of the two contagions and use the formal framework of discrete dynamical systems. In particular, we study an optimization problem where the goal is to minimize the total number of new infections subject to a budget constraint on the total number of available vaccinations for the contagions. While this problem has been considered in the literature for a single contagion, our work considers the simultaneous propagation of two contagions. This optimization problem is NPhard. We present two main solution approaches for the problem, namely an integer linear programming (ILP) formulation to obtain optimal solutions and a heuristic based on a generalization of the set cover problem. We carry out a comprehensive experimental evaluation of our solution approaches using many realworld networks. The experimental results show that our heuristic algorithm produces solutions that are close to the optimal solution and runs several orders of magnitude faster than the ILPbased approach for obtaining optimal solutions. We also carry out sensitivity studies of our heuristic algorithm.more » « less

Networkrepresentationsofsociophysicalsystemsareubiquitous,examplesbeingsocial(media)networks and infrastructurenetworkslikepowertransmissionandwatersystems.Themanysoftwaretoolsthatanalyze and visualizenetworks,andcarryoutsimulationsonthem,requiredifferentgraphformats.Consequently, it isimportanttodevelopsoftwareforconvertinggraphsthatarerepresentedinagivensourceformatintoa required representationinadestinationformat.Fornetworkbasedcomputations,graphconversionisakey capability thatfacilitatesinteroperabilityamongsoftwaretools.Thispaperdescribessuchasystemcalled GraphTrans to convertgraphsamongdifferentformats.Thissystemispartofanewcyberinfrastructure for networksciencecalled net.science. Wepresentthe GraphTrans system designandimplementation, results fromaperformanceevaluation,andacasestudytodemonstrateitsutility.more » « less

Wedescribeasoftwaresystemcalled ExecutionManager (abbreviated EM) thatcontrolstheexecutionof thirdparty software(TPS)foranalyzingnetworks.Basedonaconfigurationfilethatcontainsaspecification for theexecutionofeachTPS,thesystemlaunchesanynumberofstandaloneTPScodes,iftheprojected executiontimeandthegraphsizearewithinuserimposedlimits.Asystemcapabilityistoestimate the runningtimeofaTPScodeonagivennetworkthroughregressionanalysis,tosupportexecution decisionmaking by EM. Wedemonstratetheusefulnessof EM in generatingnetworkstructureparameters and distributions,andinextractingmetadatainformationfromtheseresults.Weevaluateitsperformance on directedandundirected,simpleandmultiedgegraphsthatrangeinsizeoversevenordersofmagnitude in numbersofedges,upto1.5billionedges.Thesoftwaresystemispartofacyberinfrastructurecalled net.science for networkscience.more » « less

Networks are pervasive in society: infrastructures (e.g., telephone), commercial sectors (e.g., banking), and biological and genomic systems can be represented as networks. Consequently, there are software libraries that analyze networks. Containers (e.g., Docker, Singularity), which hold both runnable codes and their execution environments, are increasingly utilized by analysts to run codes in a platformindependent fashion. Portability is further enhanced by not only providing software library methods, but also the driver code (i.e., main() method) for each library method. In this way, a user only has to know the invocation for the main() method that is in the container. In this work, we describe an automated approach for generating a main() method for each software library method. A single intermediate representation (IR) format is used for all library methods, and one IR instance is populated for one library method by parsing its comments and method signature. An IR for the main() method is generated from that for the library method. A source code generator uses the main() method IR and a set of small, handgenerated source code templateswith variables in the templates that are automatically customized for a particular library methodto produce the source code main() method. We apply our approach to two widely used software libraries, SNAP and NetworkX, as exemplars, which combined have over 400 library methods.more » « less

Network representations of sociophysical systems are ubiquitous, examples being social (media) networks and infrastructure networks like power transmission andwater systems. The many software tools that analyze and visualize networks, and carry out simulations on them, require different graph formats. Consequently, it is important to develop software for converting graphs that are represented in a given source format into a required representation in a destination format. For networkbased computations, graph conversion is a key capability that facilitates interoperability among software tools. This paper describes such a system called GraphTrans to convert graphs among different formats. This system is part of a new cyberinfrastructure for network science called net.science. We present the GraphTrans system design and implementation, results from a performance evaluation, and a case study to demonstrate its utility.more » « less

We describe a software system called ExecutionManager (abbreviated EM) that controls the execution of thirdparty software (TPS) for analyzing networks. Based on a configuration file that contains a specification for the execution of each TPS, the system launches any number of standalone TPS codes, if the projected execution time and the graph size are within userimposed limits. A system capability is to estimate the running time of a TPS code on a given network through regression analysis, to support execution decisionmaking by EM. We demonstrate the usefulness of EM in generating network structure parameters and distributions, and in extracting metadata information from these results. We evaluate its performance on directed and undirected, simple and multiedge graphs that range in size over seven orders of magnitude in numbers of edges, up to 1.5 billion edges. The software system is part of a cyberinfrastructure called net.science for network science.more » « less

null (Ed.)We consider the simultaneous propagation of two contagions over a social network. We assume a threshold model for the propagation of the two contagions and use the formal framework of discrete dynamical systems. In particular, we study an optimization problem where the goal is to minimize the total number of infected nodes subject to a budget constraint on the total number of nodes that can be vaccinated. While this problem has been considered in the literature for a single contagion, our work considers the simultaneous propagation of two contagions. Since the optimization problem is NPhard, we develop a heuristic based on a generalization of the set cover problem. Using experiments on three realworld networks, we compare the performance of the heuristic with some baseline methods.more » « less