This doctoral work focuses on three main problems related to social networks: (1) Orchestrating Network Formation: We consider the problem of orchestrating formation of a social network having a certain given topology that may be desirable for the intended usecases. Assuming the social network nodes to be strategic in forming relationships, we derive conditions under which a given topology can be uniquely obtained. We also study the efficiency and robustness of the derived conditions. (2) Multi-phase Influence Maximization: We propose that information diffusion be carried out in multiple phases rather than in a single instalment. With the objective of achieving better diffusion, we discover optimal ways of splitting the available budget among the phases, determining the time delay between consecutive phases, and also finding the individuals to be targeted for initiating the diffusion process. (3) Scalable Preference Aggregation: It is extremely useful to determine a small number of representatives of a social network such that the individual preferences of these nodes, when aggregated, reflect the aggregate preference of the entire network. Using real-world data collected from Facebook with human subjects, we discover a model that faithfully captures the spread of preferences in a social network. We hence propose fast and reliable ways of computing a truly representative aggregate preference of the entire network. In particular, we develop models and methods for solving the above problems, which primarily deal with formation and analysis of social networks.
We study the problem of optimally investing in nodes of a social network in a competitive setting, wherein two camps attempt to maximize adoption of their opinions by the population. Using a natural model of opinion dynamics, we formulate the problem as a zero-sum game with the players being the two camps. We first study optimal strategies of both camps in the fundamental setting where each camp aims to drive the average opinion of the population in its favor. We consider several settings of the problem, namely, when one of the camps has uncertain information about the values of the model parameters, when a camp aims at maximizing competitor's investment required to drive the average opinion in its favor, and when the influence of a camp on a node is a concave function of its investment on that node. We also study the problem under common coupled constraints on the combined investments by the camps and derive optimal strategies of the two camps, and hence show an interesting relation between the maxmin and minmax values. For a quantitative and illustrative study, we conduct simulations on real-world datasets and provide results and insights.
Jun 29 2017 cs.SI
We study the problem of inferring network topology from information cascades, in which the amount of time taken for information to diffuse across an edge in the network follows an unknown distribution. Unlike previous studies, which assume knowledge of these distributions, we only require that diffusion along different edges in the network be independent together with limited moment information (e.g., the means). We introduce the concept of a separating vertex set for a graph, which is a set of vertices in which for any two given distinct vertices of the graph, there exists a vertex whose distance to them are different. We show that a necessary condition for reconstructing a tree perfectly using distance information between pairs of vertices is given by the size of an observed separating vertex set. We then propose an algorithm to recover the tree structure using infection times, whose differences have means corresponding to the distance between two vertices. To improve the accuracy of our algorithm, we propose the concept of redundant vertices, which allows us to perform averaging to better estimate the distance between two vertices. Though the theory is developed mainly for tree networks, we demonstrate how the algorithm can be extended heuristically to general graphs. Simulation results suggest that our proposed algorithm performs better than some current state-of-the-art network reconstruction methods.
Multiplex networks describe a large number of complex social, biological and transportation networks where a set of nodes is connected by links of different nature and connotation. Here we uncover the rich community structure of multiplex networks by associating a community to each multilink where the multilinks characterize the connections existing between any two nodes of the multiplex network. Our community detection method reveals the rich interplay between the mesoscale structure of the multiplex networks and their multiplexity. For instance some nodes can belong to many layers and few communities while others can belong to few layers but many communities. Moreover the multilink communities can be formed by a different number of relevant layers. These results point out that mesoscopically there can be large differences in the compressibility of multiplex networks.
Identifying the factors which influence academic performance is an essential part of educational research. Previous studies have documented the importance of personality traits, class attendance, and social network structure. However, because most of these analyses were based on a single behavioral aspect and/or small sample sizes, we lack a quantification of the interplay of these factors. Here, we infer the academic performance among a cohort of almost 1,000 freshmen based on data collected through smartphones, which the students used as their primary phone for two years. The availability of multi-channel data from a single population allows us to directly compare the predictive power of individual and social characteristics. We find that a student's performance is best inferred from their social ties. Network indicators out-perform models based on individual characteristics. We confirm earlier findings indicating that class attendance is the most important predictor among the individual characteristics. Finally, our results indicates potential presence of strong homophily and/or peer effects among university students.