Socio-spatial influence maximization in location-based social networks

Abstract

Identifying influential nodes in social networks is a key issue in many domains such as sociology, economy, biology, and marketing. A common objective when studying such networks is to find the minimum number of nodes with the highest influence. One might for example, maximize information diffusion in social networks by selecting some appropriate nodes. This is known as the Influence Maximization Problem (IMP). Considering the social aspect, most of the current works are based on the number, intensity, and frequency of node relations. On the spatial side, the maximization problem is denoted as the Location-Aware Influence Maximization Problem (LAIMP). When advertising for a new product, having access to people who have the highest social status and their neighbors are distributed evenly across a given region is often a key issue to deal with. Another valuable issue is to inform the maximum number of users located around an event, denoted as a query point, as quickly as possible. The research presented in this paper, along with a new measure of centrality that both considers network and spatial properties, extends the influence maximization problem to the locationbased social networks and denotes it hereafter as the Socio-Spatial Influence Maximization Problem (SSIMP). The focus of this approach is on the neighbor nodes and the concept of line graph as a possible framework to reach and analyze these neighbor nodes. Furthermore, we introduce a series of local and global indexes that take into account both the graph and spatial properties of the nodes in a given network. Moreover, additional semantics are considered in order to represent the distance to a query point as well as the measure of weighted farness. Overall, these indexes act as the components of the feature vectors and using k-nearest neighbors, the closest nodes to the ‘ideal’ node are determined as top-k nodes. The node with maximum values for feature vectors is considered as the ‘ideal’ node. The experimental evaluation shows the performance of the proposed method in determining influential nodes to maximize the socio-spatial influence in location-based social networks.