Spatial and social diffusion of information and influence: models and algorithms (2012)

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. \n\nIn 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. \n\nFirst, 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.\n \nSecond, 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. \n\nThird, 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. \n\nThis 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.