Link prediction in signed social networks is challenging because of the existence and imbalance of the three kinds of social status (positive, negative and no-relation). Furthermore, there are a variety types of no-relation status in reality, e.g., strangers and frenemies, which cannot be well distinguished from the other linked status by existing approaches. In this paper, we propose a novel Framework of Integrating both Latent and Explicit features (FILE), to better deal with the no-relation status and improve the overall link prediction performance in signed networks. In particular, we design two latent features from latent space and two explicit features by extending social theories, and learn these features for each user via matrix factorization with a specially designed ranking-oriented loss function. Experimental results demonstrate the superior of our approach over state-of-the-art methods.

For real-world mobile applications such as location-based advertising and spatial crowdsourcing, a key to success is targeting mobile users that can maximally cover certain locations in a future period. To find an optimal group of users, existing methods often require information about users' mobility history, which may cause privacy breaches. In this paper, we propose a method to maximize mobile crowd's future location coverage under a guaranteed location privacy protection scheme. In our approach, users only need to upload one of their frequently visited locations, and more importantly, the uploaded location is obfuscated using a geographic differential privacy policy. We propose both analytic and practical solutions to this problem. Experiments on real user mobility datasets show that our method significantly outperforms the state-of-the-art geographic differential privacy methods by achieving a higher coverage under the same level of privacy protection.

In this paper, we propose a fractional preference model for the facility location game with two facilities that serve the similar purpose on a line where each agent has his location information as well as fractional preference to indicate how well they prefer the facilities. The preference for each facility is in the range of [0, L] such that the sum of the preference for all facilities is equal to 1. The utility is measured by subtracting the sum of the cost of both facilities from the total length L where the cost of facilities is defined as the multiplication of the fractional preference and the distance between the agent and the facilities. We first show that the lower bound for the objective of minimizing total cost is at least Ω(n^1/3). Hence, we use the utility function to analyze the agents' satification. Our objective is to place two facilities on [0, L] to maximize the social utility or the minimum utility. For each objective function, we propose deterministic strategy-proof mechanisms. For the objective of maximizing the social utility, we present an optimal deterministic strategy-proof mechanism in the case where agents can only misreport their locations. In the case where agents can only misreport their preferences, we present a 2-approximation deterministic strategy-proof mechanism. Finally, we present a 4-approximation deterministic strategy-proof mechanism and a randomized strategy-proof mechanism with an approximation ratio of 2 where agents can misreport both the preference and location information. Moreover, we also give a lower-bound of 1.06. For the objective of maximizing the minimum utility, we give a lower-bound of 1.5 and present a 2-approximation deterministic strategy-proof mechanism where agents can misreport both the preference and location.

Time-inconsistency refers to a paradox in decision making where agents exhibit inconsistent behaviors over time. Examples are procrastination where agents tend to postpone easy tasks, and abandonments where agents start a plan and quit in the middle. To capture such behaviors and to quantify inefficiency caused by such behaviors, Kleinberg and Oren (2014) propose a graph model with a certain cost structure and initiate the study of several interesting computation problems: 1) cost ratio: the worst ratio between the actual cost of the agent and the optimal cost, over all the graph instances; 2) motivating subgraph: how to motivate the agent to reach the goal by deleting nodes and edges; 3) Intermediate rewards: how to incentivize agents to reach the goal by placing intermediate rewards. Kleinberg and Oren give partial answers to these questions, but the main problems are open. In this paper, we give answers to all three open problems. First, we show a tight upper bound of cost ratio for graphs, and confirm the conjecture by Kleinberg and Oren that Akerlof’s structure is indeed the worst case for cost ratio. Second, we prove that finding a motivating subgraph is NP-hard, showing that it is generally inefficient to motivate agents by deleting nodes and edges in the graph. Last but not least, we show that computing a strategy to place minimum amount of total reward is also NP-hard and we provide a 2n- approximation algorithm.

We rethink the link prediction problem in signed social networks by also considering "no-relation" as a future status of a node pair, rather than simply distinguishing positive and negative links proposed in the literature. To understand the underlying mechanism of link formation in signed networks, we propose a feature framework on the basis of a thorough exploration of potential features for the newly identified problem. Grounded on the framework, we also design a trinary classification model, and experimental results show that our method outperforms the state-of-the-art approaches.