The Internet represents a unique opportunity for people to interact with each other across time and space, and online communities have existed long before the Internet's solidification in everyday living. There are two inherent challenges that online communities continue to contend with: motivating participation and organizing information. An online community's success or failure rests on the content generated by its users. Specifically, users need to continually participate by contributing new content and organizing existing content for others to be attracted and retained. I propose both participation and organization can be enhanced if users have an explicit awareness of the implicit social network which results from their online interactions. My approach makes this normally ``hidden" social network visible and shows users that these intangible relations have an impact on satisfying their information needs and vice versa. That is, users can more readily situate their information needs within social processes, understanding that the value of information they receive and give is influenced and has influence on the mostly incidental relations they have formed with others. First, I describe how to model a social network within an online discussion forum and visualize the subsequent relationships in a way that motivates participation. Second, I show that social networks can also be modeled to generate recommendations of information items and that, through an interactive visualization, users can make direct adjustments to the model in order to improve their personal recommendations. I conclude that these modeling and visualization techniques are beneficial to online communities as their social capital is enhanced by "weaving" users more tightly together.

The Internet represents a unique opportunity for people to interact with each other across time and space, and online communities have existed long before the Internet's solidification in everyday living. There are two inherent challenges that online communities continue to contend with: motivating participation and organizing information. An online community's success or failure rests on the content generated by its users. Specifically, users need to continually participate by contributing new content and organizing existing content for others to be attracted and retained. I propose both participation and organization can be enhanced if users have an explicit awareness of the implicit social network which results from their online interactions. My approach makes this normally ``hidden" social network visible and shows users that these intangible relations have an impact on satisfying their information needs and vice versa. That is, users can more readily situate their information needs within social processes, understanding that the value of information they receive and give is influenced and has influence on the mostly incidental relations they have formed with others. First, I describe how to model a social network within an online discussion forum and visualize the subsequent relationships in a way that motivates participation. Second, I show that social networks can also be modeled to generate recommendations of information items and that, through an interactive visualization, users can make direct adjustments to the model in order to improve their personal recommendations. I conclude that these modeling and visualization techniques are beneficial to online communities as their social capital is enhanced by "weaving" users more tightly together.

With the ubiquity of broadband, wireless and mobile networking and the diversity of user-driven social networks and social channels, we are entering an information age where people and vehicles are connected at all times, and information and influence are diffused continuously through not only traditional authoritative media such as news papers, TV and radio broadcasting, but also user-driven new channels for disseminating information and diffusing influence. Social network users and mobile travelers can influence and be influenced by the social and spatial connectivity that they share through an impressive array of social and spatial channels, ranging from friendship, activity, professional or social groups to spatial, location-aware, and mobility aware events. In this dissertation research, we argue that spatial alarms and activity-based social networks are two fundamentally new types of information and influence diffusion channels. Such new channels have the potential of enriching our professional experiences and our personal life quality in many unprecedented ways. For instance, spatial alarms enable people to share their experiences or disseminate certain points of interest by leaving location-dependent greetings, tips or graffiti and location dependent tour guide to their friends, colleagues and family members. Through social networks, people can influence their friends and colleagues by the activities they have engaged, such as reviews and blogs on certain events or products. More interestingly, the power of such spatial and social diffusion of information and influence can go far beyond our physical reach. People can utilize user-generated social and spatial channels as effective means to disseminate information and propagate influence to a much wider and possibly unknown range of audiences and recipients at any time and in any location. A fundamental challenge in embracing such new and exciting ways of information diffusion is to develop effective and scalable models and algorithms as enabling technology and building blocks. This dissertation research is dedicated towards this ultimate objective with three novel and unique contributions. First, we develop an activity driven and self-configurable social influence model and a suite of computational algorithms to compute and rank social network nodes in terms of activity-based influence diffusion over social network topologies. By activity driven we mean that the real impact of social influence and the speed of such influence propagation should be computed based on the type, the amount and the time window of the activities performed by a social network node in addition to its social connectivity (social network topology). By self-configurable we mean that the diffusion efficiency and effectiveness are dynamically adapted based on the settings and tunings of multiple spatial and social parameters such as diffusion context, diffusion location, diffusion rate, diffusion energy (heat), diffusion coverage and diffusion incentives (e.g., reward points), to name a few. We evaluate our approach through datasets collected from Facebook, Epinions, and DBLP datasets. Our experimental results show that our activity based social influence model outperforms existing topology-based social influence model in terms of effectiveness and quality with respect to influence ranking and influence coverage computation. Second, we further enhance our activity based social influence model along two dimensions. At first, we use a probabilistic diffusion model to capture the intrinsic properties of social influence such that nodes in a social network may have the choice of whether to participate in a social influence propagation process. We examine threshold based approach and independent probabilistic cascade based approach to determine whether a node is active or inactive in each round of influence diffusion. Secondly, we introduce incentives using multi-scale reward points, which are popularly used in many business settings. We then examine the effectiveness of reward points based incentives in stimulating the diffusion of social influences. We show that given a set of incentives, some active nodes may become more active whereas some inactive nodes may become active. Such dynamics changes the composition of the top-k influential nodes computed by activity-based social influence model. We make several interesting observations: First, popular users who are high degree nodes and have many friends are not necessarily influential in terms of spawning new activities or spreading ideas and information. Second, most influential users are more active in terms of their participation in the social activities and interactions with their friends in the social network. Third, multi-scale reward points based incentives can be effective to both inactive nodes and active nodes. Third, we introduce spatial alarms as the basic building blocks for location-dependent information sharing and influence diffusion. People can share and disseminate their location based experiences and points of interest to their friends and colleagues in the form of spatial alarms. Spatial alarms are triggered and delivered to the intended subscribers only when the subscribers move into the designated geographical vicinity of the spatial alarms, enabling delivering and sharing of relevant information and experience at the right location and the right time with the right subscribers. We studied how to use locality filters and subscriber filers to enhance the spatial alarm processing using traditional spatial indexing techniques. In addition, we develop a fast spatial alarm indexing structure and algorithms, called Mondrian Tree, and demonstrate that the Mondrian tree enabled spatial alarm system can significantly outperform existing spatial indexing based solutions such as R-tree, $k$-d tree, Quadtree. This dissertation consists of six chapters. The first chapter introduces the research hypothesis. We describe our activity-based social influence model in Chapter 2. Chapter 3 presents the probabilistic social influence model powered with rewards incentives. We introduce spatial alarms and the basic system architecture for spatial alarm processing in Chapter 4. We describe the design of our Mondrian tree index of spatial alarms and alarm free regions in Chapter 5. In Chapter 6 we conclude the dissertation with a summary of the unique research contributions and a list of open issues closely relevant to the research problems and solution approaches presented in this dissertation.

Chapter one shows that US households with high unconditional and cyclical labor income risk are more leveraged and allocate a greater share of their financial assets to stocks. I use self-reported risk preferences to show that rational sorting of risk tolerant workers into risky employment is responsible for this otherwise puzzling result. With risk preferences accounted for, I find evidence that households with greater permanent income variance reduce leverage and stock allocations to an extent consistent with theory. However, household portfolios and employment selection do not respond significantly to any of the other three forms of labor income risk I measure: disaster risk, permanent income cyclicality, and permanent income variance cyclicality. Chapter two reports evidence that individual investors in Indian equities hold better performing portfolios as they become more experienced in the equity market. Experienced investors tilt their portfolios profitably towards value stocks and stocks with low turnover, but these tilts do not fully explain their performance. Experienced investors also tend to have lower turnover and disposition bias. These behaviors, as well as underdiversification, diminish when investors experience poor returns resulting from them, consistent with models of reinforcement learning. Furthermore, Indian stocks held by experienced, well diversified, low-turnover and low-disposition-bias investors deliver higher average returns even controlling for a standard set of stock-level characteristics. Chapter three shows that news reflected by industry stock returns is only gradually incorporated into stock prices in other countries. Information links between cross-border portfolios play a significant role in explaining variation in the speed of this incorporation; responses to industry news are rapid across borders where portfolios share more crosslistings, equity analyst coverage, and a greater common equity investor base. The drift in returns following cross-border industry news has halved in the past 25 years. About half of this change relates to a growth in information links and reductions in expropriations risks facing foreign investors. A simple long-short trading strategy designed to exploit gradual diffusion of industry news across borders appears profitable, but is unlikely to yield returns as high as the 8 to 9 percent annual rate the strategy has returned historically. / Economics

Web and mobile technologies have had such profound impact that we have witnessed significant evolutionary changes in our social, economic and cultural activities. In recent years, online social networking sites such as Twitter, Facebook, Google+, and LinkedIn have gained immense popularity. Such social networks have led to an enormous explosion of network-centric data in a wide variety scenarios, posing unprecedented analytical and computational challenges to MIS researchers. At the same time, the availability of such data offers major research opportunities in various social computing and analytics areas to tackle interesting questions such as: - From a business and marketing perspective, how to mine the novel datasets of online user activities, interpersonal communications and interactions, for developing more successful marketing strategies? - From a system development perspective, how to incorporate massive amounts of available data to assist online users to find relevant, efficient, and timely information? In this dissertation, I explored these research opportunities by studying multiple analytics problems arose from the design and use of social networking services. The first two chapters (Chapter 2 and 3) are intended to study how social network can help to derive a better estimation of customer lifetime value (CLV), in the social gaming context. In Chapter 2, I first conducted an empirical study to demonstrate that friends' activities can serve as significant indicators of a player's CLV. Based on this observation, I proposed a perceptron-based online CLV prediction model considering both individual and friendship information. Preliminary results have shown that the model can be effectively used in online CLV prediction, by evaluating against other commonly-used benchmark methods. In Chapter 3, I further extended the metric of traditional CLV, by incorporating the personal influences on other customers' purchase as an integral part of the lifetime value. The proposed metric was illustrated and tested on seven social games of different genres. The results showed that the new metric can help marketing managers to achieve more successful marketing decisions in user acquisition, user retention, and cross promotion. Chapter 4 is devoted to the design of a recommendation system for micro-blogging. I studied the information diffusion pattern in a micro-blogging site (Twitter.com) and proposed diffusion-based metrics to assess the quality of micro-blogs, and leverage the new metric to implement a novel recommendation framework to help micro-blogging users to efficiently identify quality news feeds. Chapter 5 concludes this dissertation by highlighting major research contributions and future directions.

Understanding information diffusion on complex networks is a key issue from a theoretical and applied perspective. Epidemiology-inspired SIR models have been proposed to model information diffusion. Recent papers have analyzed this question from a data-driven perspective. We complement these findings investigating if epidemic models calibrate with a systematic procedure are capable of reproducing key spreading cascade properties. We first identify a large-scale, rich dataset from which we can reconstruct the diffusion trail and the underlying network. Secondly, we examine the simple SIR model as a baseline model and conclude that it was unable to generate structurally realistic spreading cascades. We found the same result examining model extensions to which take into account heterogeneities observed in the data. In contrast, other models which take into account time patterns available in the data generate qualitatively more similar cascades. Although one key property was not reproduced in any model, this result highlights the importance of taking time patterns into account. We have also analyzed the impact of the underlying network structure on the models examined. In our data the observed cascades were constrained in time, so we could not rely on the theoretical results relating the asymptotic behavior of the epidemic and network topological features. Performing simulations we assessed the impact of these common topological properties in time-bounded epidemic and identified that the distribution of neighbors of seed nodes had the most impact among the investigated properties in our context. We conclude discussing identifying perspectives opened by this work.

abstract: Diffusion processes in networks can be used to model many real-world processes, such as the propagation of a rumor on social networks and cascading failures on power networks. Analysis of diffusion processes in networks can help us answer important questions such as the role and the importance of each node in the network for spreading the diffusion and how to top or contain a cascading failure in the network. This dissertation consists of three parts. In the first part, we study the problem of locating multiple diffusion sources in networks under the Susceptible-Infected-Recovered (SIR) model. Given a complete snapshot of the network, we developed a sample-path-based algorithm, named clustering and localization, and proved that for regular trees, the estimators produced by the proposed algorithm are within a constant distance from the real sources with a high probability. Then, we considered the case in which only a partial snapshot is observed and proposed a new algorithm, named Optimal-Jordan-Cover (OJC). The algorithm first extracts a subgraph using a candidate selection algorithm that selects source candidates based on the number of observed infected nodes in their neighborhoods. Then, in the extracted subgraph, OJC finds a set of nodes that "cover" all observed infected nodes with the minimum radius. The set of nodes is called the Jordan cover, and is regarded as the set of diffusion sources. We proved that OJC can locate all sources with probability one asymptotically with partial observations in the Erdos-Renyi (ER) random graph. Multiple experiments on different networks were done, which show our algorithms outperform others. In the second part, we tackle the problem of reconstructing the diffusion history from partial observations. We formulated the diffusion history reconstruction problem as a maximum a posteriori (MAP) problem and proved the problem is NP hard. Then we proposed a step-by- step reconstruction algorithm, which can always produce a diffusion history that is consistent with the partial observations. Our experimental results based on synthetic and real networks show that the algorithm significantly outperforms some existing methods. In the third part, we consider the problem of improving the robustness of an interdependent network by rewiring a small number of links during a cascading attack. We formulated the problem as a Markov decision process (MDP) problem. While the problem is NP-hard, we developed an effective and efficient algorithm, RealWire, to robustify the network and to mitigate the damage during the attack. Extensive experimental results show that our algorithm outperforms other algorithms on most of the robustness metrics. / Dissertation/Thesis / Doctoral Dissertation Electrical Engineering 2018

Les services de microblogging (comme Twitter ou Sina Weibo) sont devenu ces dernières années des plateformes très importantes de partage d'information sur l'Internet. Les microblogs sont fréquemment utilisé pour l'analyse de l'opinion, le marketing viral, et les campagnes politiques. Comprendre les mécanismes sous-jacents de la diffusion d'information sur les microblogs et comment des contenus deviennent populaires est important.L‘analyse de la diffusion d'information dans les microblogs nécessite la collecte de donnée des microblogs, la modélisation de la diffusion d'information et l'application des modèles résultants. Traiter les données massives issues des microblogs est un défi en soi. Concevoir des algorithmes efficaces et sans biais afin d'échantillonner les microblogs est ainsi fondamental. Ceci doit prendre en compte la complexité du phénomène de « retweet » qui dépend de la valeur éphémère de l'information, de la topologie du réseau de microblogging et des caractéristiques particulières des éditeurs et retweeteurs.Deux modèles ont été traditionnellement appliqués à la diffusion d'information : les cascades indépendantes et modèle à seuil linéaire. Aucun de ces deux modèles n'est à même de décrire le processus du retweeting de façon correcte. Il devient donc nécessaire de de caractériser la diffusion d'information. De plus, une description complète de la relation entre la diffusion d'information dans les microblogs et de popularité des termes recherchés sur Internet serait utile.Ces travaux de thèse présentent une analyse complète de la diffusion d'information dans les microblogs. Les contributions ce cette thèse sont les suivantes :1) Il y'a deux technique d'échantillonnage sans biais pour les réseaux sociaux : la marche aléatoire de Métropolis-Hastings (MHRW), et la méthode d'échantillonnage sans biais de graphes dirigés (USDSG). Néanmoins ces deux méthodes peuvent aboutit à un taux important d'auto-échantillonnage quand elles sont appliquées à des microblogs. Pour résoudre ce problème, j'ai modélisé l'échantillonnage d'un OSN par un processus de Markov et j'en ai déduit les conditions nécessaires et suffisantes d'un échantillonnage sans biais. Ces conditions m'ont permis de proposer un algorithme d'échantillonnage sans biais et efficace que j'ai nommé : échantillonnage sans biais par liens vide (USDE). Cette nouvelle méthode d'échantillonage réduit fortement l'auto-échantillonnage du MHRW. L ‘évaluation empirique montre que la moyenne des dégrées des nœuds échantillonnés est proche de la vérité terrain alors que pour MHRW et USDSG elle est 2 à 4 fois supérieure.2) La seconde contribution de cette thèse vise les lacunes des modèles en cascades indépendantes et de seuils linéaires. J'ai développé un modèle fondé sur les processus de Galton-Watson avec mort (GWK) qui prennent en compte tous les facteurs importants du processus de retweet. Ce nouveau modèle est validé par une application sur des données issues de Twitter et de Weibo.3) La troisième contribution est relative au développement d'un modèle économique du marché des acteurs actifs dans le domaine du marketing sur les mots clés dans les sites de recherches. J'ai développé des méthodes de gestion de portfolios de mots clés et montrés que ces portfolios permettent d'améliorer fortement les rendements sans augmenter le niveau de risque. / Microblog service (such as Twitter and Sina Weibo) have become an important platform for Internet content sharing. As the information in Microblog are widely used in public opinion mining, viral marketing and political campaigns, understanding how information diffuses over Microblogs, and explaining the process through which some tweets become popular, are important.The analysis of the information diffusion in Microblogs involves the data collection from Microblog, the modeling on information spreading and using the resulting models. Dealing with the huge amount of data flowing through microblogs is by itself a challenge. Designing an efficient and unbiased sampling algorithm for Microblog is therefore essential. Besides, the retweeting process in Microblog is complex because of the ephemerality of information, the topology of Microblog network and the particular features (such as number of followers) of publisher and retweeters.Two traditional models have been used for information diffusion : Independent Cascades and Linear Threshold models. However no one of them can describe completely the retweeting process in Microblog accurately. The analysis and design of new models to characterize the information diffusion in Microblog is therefore necessary. Moreover, a comprehensive description of the correlation between the information diffusion in Microblog and the searching trends of keywords on search engines is lacking although some work has been found some preliminary relationships.This work presnets a complete analysis of information diffusion in Microblog from. The contributions and innovations of this thesis are as follows:1)There are two popular unbiased Online Social Network (OSN) sampling algorithms,Metropolis-Hastings Random Walk (MHRW) and Unbiased Sampling for Directed Social Graph (USDSG) method. However they are both likely to yield considerable self-sampling probabilities when applied to Microblogs where there is local. To solve this problem, I have modelled the process of OSN sampling as a Markov process and have deduced the sufficient and necessary conditions of unbiased sampling. Based on this unbiased conditions, I proposed an efficient and unbiased sampling algorithms, Unbiased Sampling method with Dummy Edges (USDE), which reduces strongly the self-sampling probabilities of MHRW. The experimental evaluation demonstrate thats the average node degree of samples of MHRW and USDSG is 2 - 4 times as high as the ground truth while USDE can provide the approximation of ground truth when the sampling repetitions are removed. Moreover the average sampling time per node in USDE is only a half of MHRW and USDSG one.2)A second contribution targets the shortages of Independent Cascades (IC) and Linear Threshold (LT) models in characterizing the retweeting process in Microblogs. I achieve this by introducing a Galton Watson with Killing (GWK) model which considers all the three important factors including the ephemerality of information, the topology of network and the features of publisher and retweeters accurately. We have validated the applicability of the of GWK model over two datasets from Sina Weibo and Twitter and showed that GWK model can fit 82% of information receivers and 90% of the maximum numbers of hops in the real retweeting process. Besides, the GWK model is useful for revealing the endogenous and exogenous factors which affect the popularity of tweets.3) Motivated by the correlation between popularity and trendiness of topicsin Microblog and search trends, I have developed an economic analysis of the market involving a third-party ad broker, which is a popular market in current SEM, and finds that the adwords augmenting strategy with the trending and popular topics in Twitter enables the broker to achieve, on average, four folds larger return on investment than with a non-augmented strategy, while still maintaining the same level of risk.

Dans cette thèse, nous présentons à la fois une collection de modèles de générations de réseaux et de diffusion d'information exprimés à l'aide d'un formalisme particulier appelé la réécriture de graphes, ainsi qu'une nouvelle méthode de représentation permettant la visualisation de la diffusion d'information dans des grands réseaux sociaux. Les graphes sont des objets mathématiques particulièrement versatiles qui peuvent être utilisés pour représenter une large variété de systèmes abstraits. Ces derniers peuvent être transformés de multiples façons (création, fusion ou altération de leur éléments), mais de telles modifications doivent être contrôlées afin d'éviter toute opération non souhaitée. Pour cela, nous faisons appel au formalisme particulier de la réécriture de graphes afin d'encadrer et de contrôler toutes les transformations. Dans notre travail, un système de réécriture de graphes opère sur un graphe, qui peut être transformé suivant un ensemble de règles, le tout piloté par une stratégie. Nous commençons tout d'abord par utiliser la réécriture en adaptant deux algorithmes de génération de réseaux, ces derniers permettant la création de réseaux aux caractéristiques petit monde. Nous traduisons ensuite vers le formalisme de réécriture différents modèles de diffusion d'information dans les réseaux sociaux. En énonçant à l'aide d'un formalisme commun différents algorithmes, nous pouvons plus facilement les comparer, ou ajuster leurs paramètres. Finalement, nous concluons par la présentation d'un nouvel algorithme de dessin compact de grands réseaux sociaux pour illustrer nos méthodes de propagation d'information. / In this thesis, we present a collection of network generation and information diffusion models expressed using a specific formalism called strategic located graph rewriting, as well as a novel network layout algorithm to show the result of information diffusion in large social networks. Graphs are extremely versatile mathematical objects which can be used to represent a wide variety of high-level systems. They can be transformed in multiple ways (e.g., creating new elements, merging or altering existing ones), but such modifications must be controlled to avoid unwanted operations. To ensure this point, we use a specific formalism called strategic graph rewriting. In this work, a graph rewriting system operates on a single graph, which can then be transformed according to some transformation rules and a strategy to steer the transformation process. First, we adapt two social network generation algorithms in order to create new networks presenting small-world characteristics. Then, we translate different diffusion models to simulate information diffusion phenomena. By adapting the different models into a common formalism, we make their comparison much easier along with the adjustment of their parameters. Finally, we finish by presenting a novel compact layout method to display overviews of the results of our information diffusion method.

Social networks are everywhere, from face-to-face activities to online social networks such as Flickr, YouTube and Facebook. In social networks, ties (relationships) are connections between people. The change of social relationships over time consequently leads to the evolution of the social network structure. At the same time, ties serve as carriers to transfer pieces of information from one person to another. Studying social ties is critical to understanding the fundamental processes behind the network. Although many studies on social networks have been carried out over the last many decades, most of the work either used small in-lab datasets, or focused on directly connected static relations while ignoring indirect relations and the dynamic nature of real networks. Today, because of the emergence of online social networks, more and more large longitudinal social datasets are becoming available. The available real social datasets are fundamental to understanding evolution processes of networks in more depth. In this thesis, we study the role of social ties in dynamic networks using datasets from various domains of online social networks. Networks, especially social networks often exhibit dual dynamic nature: the structure of the graph changes (by node and edge insertion and removal), and information flows in the network. Our work focuses on both aspects of network dynamics. The purpose of this work is to better understand the role of social ties in network evolution and changes over time, and to determine what social factors help shape individuals’ choices in negative behavior. We first developed a metric that measures the strength of indirectly connected ties. We validated the accuracy of the measurement of indirect tie metric with real-world social datasets from four domains. Another important aspect of my research is the study of edge creation and forecast future graph structure in time evolving networks. We aim to develop algorithms that explain the edge formation properties and process which govern the network evolution. We also designed algorithms in the information propagation process to identify next spreaders several steps ahead, and use them to predict diffusion paths. Next, because different social ties or social ties in different contexts have different influence between people, we looked at the influence of social ties in behavior contagion, particularly in a negative behavior cheating. Our recent work included the study of social factors that motivate or limit the contagion of cheating in a large real-world online social network. We tested several factors drawn from sociology and psychology explaining cheating behavior but have remained untested outside of controlled laboratory experiments or only with small, survey based studies. In addition, this work analyzed online social networks with large datasets that certain inherent influences or patterns only emerge or become visible when dealing with massive data. We analyzed the world’s largest online gaming community, Steam Community, collected data with 3, 148, 289 users and 44, 725, 277 edges. We also made interesting observations of cheating influence that were not observed in previous in-lab experiments. Besides providing empirically based understanding of social ties and their influence in evolving networks at large scales, our work has high practical importance for using social influence to maintain a fair online community environment, and build systems to detect, prevent, and mitigate undesirable influence.