ICTS

We study a market for information in one-of-a-kind services (e.g., home improvement), where an infomediary mediates contact-information between the consumer and providers. This market is a part of online platform-markets for information that have evolved since the advent of the Internet and continue unabated. Unlike online price-information markets for standardized products and services (e.g., automobile and insurance), or, platform markets for advertisements (e.g., ad exchange) and software development (e.g., apps for mobile OS) in one-of-a-kind services the deliverable is non-standardized and in fact, customized for every consumer. This necessitates considerable a priori task-specific information flow between the consumer and potential providers, who vary in cost of performing the task, and thus motivates the consumer to host bid competition among providers. In turn the infomediary may find an incentive to control the information flow between the consumer and the potential providers. Recognizing the bid-competition-based price discovery for the service, the infomediary sets fees to balance own revenue with the need of attracting both providers and consumer. Using game theoretic models, we analyze three platforms that differ in (1) whether providers or the consumer pays for contact-information, and (2) whether brief vs. detailed task-specific information is transmitted to potential providers. In the first two platforms, both high- and low-cost providers obtain contact-information, and infomediary sets a high fee to restrict competition to a deterministic number of providers; thus, its interest can be misaligned with the consumer. In a third platform, which allows detailed task-specific information flow to potential providers, only low-cost providers obtain contact-information, infomediary sets an intermediate fee to attract a probabilistic number of providers, and its interest is partially aligned with the consumer. We further compare the platforms based on infomediary revenue and social cost. In addition, we analyze data obtained from an online infomediary to draw further empirical insights.

Rumor spreading is a basic model for information dissemination in a social network. In this setting a central concern for an entity, say the service provider, is to find ways to speed up the dissemination process and to maximize the overall information spread. However, a central issue absent in this setting is that of adaptivity. How can the service provider use information about the current state of the network to cost effectively speed up the process. Motivated by the recent emergence of the so-called opportunistic communication networks, we take a novel approach by considering the issue of adaptivity in the most basic continuous time (asynchronous) rumor spreading process. In our setting a rumor has to be spread to a population and the service provider can push it at any time to any node in the network and has unit cost for doing this. On the other hand, as usual in rumor spreading, upon meeting, nodes share the rumor and this imposes no cost on the service provider. We consider the cost version of the problem with a fixed deadline and ask for a minimum cost strategy that spreads the rumor to every node. A non-adaptive strategy can only intervene at the beginning and at the end, while an adaptive strategy has full knowledge and intervention capabilities. Our main result is that in the homogeneous case (where every pair of nodes randomly meet at the same rate) the benefit of adaptivity is bounded by a constant. This requires a subtle analysis of the underlying random process that is of interest in its own right. Joint work with J.R. Correa (U. Chile), N. Olver (VU University Amsterdam; and CWI, Amsterdam), and A. Vera (U. Chile).

This tutorial will discuss how a network administrator/designer can efficiently route traffic from multiple strategic users if the routing cost is shared equally by them. I will talk about both static and dynamic settings, based on whether the set of users is fixed or users can join/leave the network over time. In both settings, I will discuss how the quality of the solution is affected by the degree of control available to the administrator. The first part of the tutorial will illustrate this by showing a sharp distinction between the price of anarchy and the price of stability of the resulting network game. This will lead us to the question of determining which of the corresponding equilibria are attainable via natural game dynamics; this will be our topic of discussion in the second part of the tutorial. The tutorial will touch upon a large body of work in the last 15 years in this area including recent developments, highlighting the main techniques developed and their shortcomings in trying to address the many outstanding questions in this domain.

This tutorial will discuss how a network administrator/designer can efficiently route traffic from multiple strategic users if the routing cost is shared equally by them. I will talk about both static and dynamic settings, based on whether the set of users is fixed or users can join/leave the network over time. In both settings, I will discuss how the quality of the solution is affected by the degree of control available to the administrator. The first part of the tutorial will illustrate this by showing a sharp distinction between the price of anarchy and the price of stability of the resulting network game. This will lead us to the question of determining which of the corresponding equilibria are attainable via natural game dynamics; this will be our topic of discussion in the second part of the tutorial. The tutorial will touch upon a large body of work in the last 15 years in this area including recent developments, highlighting the main techniques developed and their shortcomings in trying to address the many outstanding questions in this domain.

I will talk about our recent work on topology design games between a network designer and a strategic adversary. While the designer aims to defend the network or grow it to an optimal topology with respect to a network property, the adversary simultaneously counters and tries to force the designer to operate in a suboptimal topology. I will characterize some key structural properties of the mixed strategy equilibriums of this one-shot game, and then describe the effect of parameters, such as probability of a successful attack, on the topology dynamics in a repeated game setting. I will also describe a multi-stage game in which the designer is not just interested in the instantaneous network property costs but a discounted sum of costs over a period of time; and will examine whether defense/growth strategies here result in better benefits for the designer compared to the strategies resulting from the one-shot game.

Biological systems are a truly unique state of matter - active, adaptive and evolving. Cells, biological tissues, highly coordinated animal groups and interacting populations are a form of complex materials with emergent coherent properties that arise from mechanical and socially-mediated interactions between constituent elements/ individuals. Unlike in purely physical systems, a biological individual is capable of processing information, in addition to tuning dynamically adaptive response. These augmented capabilities of individual units allow a population to exhibit collective organization and behaviour, beyond what is found in traditional materials. Such a perspective naturally suggests two complementary approaches : (i) to distill unifying physical principles that govern biological systems by probing them as a unique state of matter or as a unique class of dynamical systems and (ii) to construct de novo, using traditional materials, systems with functions that are defining features of living matter such as self propulsion, replication etc. and study the resulting emergent collective behavior. In revealing the differences between the different systems, artificial and biological, as well as the underlying commonalities in mathematical features, we hope to better understand the relationship between microscopic and macroscopic emergent collective behaviour in systems far from equilibrium and ultimately, in biology. In this talk I will try to present a panoramic view of these issues through a survey of relevant work and will also touch upon some of our own proposals in this regard.

Biological systems are a truly unique state of matter - active, adaptive and evolving. Cells, biological tissues, highly coordinated animal groups and interacting populations are a form of complex materials with emergent coherent properties that arise from mechanical and socially-mediated interactions between constituent elements/ individuals. Unlike in purely physical systems, a biological individual is capable of processing information, in addition to tuning dynamically adaptive response. These augmented capabilities of individual units allow a population to exhibit collective organization and behaviour, beyond what is found in traditional materials. Such a perspective naturally suggests two complementary approaches : (i) to distill unifying physical principles that govern biological systems by probing them as a unique state of matter or as a unique class of dynamical systems and (ii) to construct de novo, using traditional materials, systems with functions that are defining features of living matter such as self propulsion, replication etc. and study the resulting emergent collective behavior. In revealing the differences between the different systems, artificial and biological, as well as the underlying commonalities in mathematical features, we hope to better understand the relationship between microscopic and macroscopic emergent collective behaviour in systems far from equilibrium and ultimately, in biology. In this talk I will try to present a panoramic view of these issues through a survey of relevant work and will also touch upon some of our own proposals in this regard.

Spread of directly transmitted infectious diseases, such as influenza, measles, etc., is strongly influenced by the structure of human contact networks. As empirical data on the networks of social contacts exhibits evidence for strong community or modular organization, it is natural to ask how do such structures affect the course of an epidemic - particularly in the long term. We report our investigations into the dynamics of models of epidemic spreading in modular networks, where individuals within a community tend to have a much higher degree of connectivity compared to the connectivity between different communities, that may provide clues for designing efficient methods of controlling human/animal pandemics. In particular, we consider the persistence of epidemic diseases for which individuals after having recovered from an infection can again become susceptible with a certain probability - modeled using SIRS (susceptible-infected-recovered-susceptible) dynamics at the agent level. We show that the disease can become recurrent depending on the mesoscopic organization of the social network. In particular, highly contagious diseases which would have become extinct in homogeneous contact networks may survive indefinitely when there is a strong community organization in the population. This suggests that introducing quarantine (or otherwise, isolating different segments of a population) for diseases with a high reproduction number may, counter-intuitively, sometimes have a negative effect in the long run.

Spread of directly transmitted infectious diseases, such as influenza, measles, etc., is strongly influenced by the structure of human contact networks. As empirical data on the networks of social contacts exhibits evidence for strong community or modular organization, it is natural to ask how do such structures affect the course of an epidemic - particularly in the long term. We report our investigations into the dynamics of models of epidemic spreading in modular networks, where individuals within a community tend to have a much higher degree of connectivity compared to the connectivity between different communities, that may provide clues for designing efficient methods of controlling human/animal pandemics. In particular, we consider the persistence of epidemic diseases for which individuals after having recovered from an infection can again become susceptible with a certain probability - modeled using SIRS (susceptible-infected-recovered-susceptible) dynamics at the agent level. We show that the disease can become recurrent depending on the mesoscopic organization of the social network. In particular, highly contagious diseases which would have become extinct in homogeneous contact networks may survive indefinitely when there is a strong community organization in the population. This suggests that introducing quarantine (or otherwise, isolating different segments of a population) for diseases with a high reproduction number may, counter-intuitively, sometimes have a negative effect in the long run.

The problem of maximizing information diffusion, given a certain budget constraint (the number of seed nodes), is an extensively studied topic in social networks research. Existing literature focuses on single phase diffusion where (a) all seed nodes are selected at the beginning of diffusion and (b) all the selected nodes are activated simultaneously. In this talk, we undertake an investigation of the effect of selecting and activating seed nodes in multiple phases. Specically, we study diffusion in two phases assuming the well-studied independent cascade model. First, we formulate an objective function for two-phase diffusion, investigate its properties, and propose e fficient algorithms for finding the seed nodes in the two phases. Next, we study two associated problems: (1) budget splitting which seeks to optimally split the total budget between the two phases and (2) scheduling which seeks to determine an optimal delay after which to commence the second phase.

Advances in the Internet and communication technologies have made it possible to harness the wisdom and efforts from a sizable portion of the society towards accomplishing tasks which are otherwise herculean. This phenomenon is popularly known as crowdsourcing. Further, an explosive growth in online social media has given a novel twist to crowdsourcing applications where participants can exploit the underlying social network for inviting their friends to help executing the task. In this talk, we discuss the problem of a planner who needs to incentivize agents within a network in order to seek their help in executing an atomic task as well as in recruiting other agents to execute the task. One key application of this work is related to digital epidemiology, where a public health organization that is responsible for monitoring and controlling the spread of an infectious disease needs to regularly and repeatedly survey, identify, and reduce the intensive sources and epidemics of the disease in a timely manner to avoid any outbreak.

The tutorial will centre around some of the classical models of diffusion and its limitations. The discussion will range from the standard SIR/SIS model, the branching processes to some of the recent open questions in epidemic modelling. Special emphasis will be on some of the state of the art ideas in knowledge networks where cognitive conflicts trigger information diffusion with incremental improvisations. We will also touch upon modeling collective action and some of the open questions pertaining to knowledge emergence in collaboration networks.

Problems in network analytics are commonplace in diverse domains, ranging from social interactions to systems biology and spread of infectious diseases. More recently, interactions between distinct networks have attracted considerable attention as well; for e.g., social networks and the spread of disease, drug similarity/ complementarity and its regulatory impact on gene expression, etc. In this talk, I will highlight the importance of statistical analysis, and its role in motivating algorithm development, in network analytics. I will present three specific examples -- statistical significance of dense clusters in random graphs, statistical significance of overlaps of clusters with applications in social networks, and statistical significance of network alignments with applications in biomolecular interaction networks. These results will be used to motivate new problems in derivation of arrival sequences in dynamic networks and tracking lineage of dynamic objects in evolving systems. In each of these problem, I will highlight the role of analytical modeling, design of suitable priors, and their impact on algorithm design.

Online social networking sites such as Facebook, Twitter and Flickr are among the most popular sites on the Web, providing platforms for sharing information and interacting with a large number of people. The different ways for users to interact, such as liking, retweeting and favoriting user-generated content, are among the defining and extremely popular features of these sites. While empirical studies have been done to learn about the network growth processes in these sites, few studies have focused on social interaction behaviour and the effect of social interaction on network growth. In this paper, we analyze large-scale data collected from the Flickr social network to learn about individual favoriting behaviour and examine the occurrence of link formation after a favorite is created. We do this using a systematic formulation of Flickr as a two-layer temporal multiplex network: the first layer describes the follow relationship between users and the second layer describes the social interaction between users in the form of favorite markings to photos uploaded by them. Our investigation reveals that (a) favoriting is well-described by preferential attachment, (b) over 50% of favorites are reciprocated within 10 days if at all they are reciprocated, (c) different kinds of favorites differ in how fast they are reciprocated, and (d) after a favorite is created, multiplex triangles are closed by the creation of follow links by the favoriter's followers to the favorite receiver.