Trust, Recommendation Systems, and Collaboration - UMD - January 2015

Public Audience
Purpose: To highlight project progress. Information is generally at a higher level which is accessible to the interested public. All information contained in the report (regions 1-3) is a Government Deliverable/CDRL.

PI(s): John S. Baras, Jennifer Golbeck
Researchers: Peixin Gao (graduate student), Xiangyang Liu (graduate student)

HARD PROBLEM(S) ADDRESSED
This refers to Hard Problems, released November 2012.

#2 (Policy-Governed Secure Collaboration);
#1 (Scalability and Composability); #5 (Understanding and Accounting for Human Behavior)

PUBLICATIONS
Papers published in this quarter as a result of this research. Include title, author(s), venue published/presented, and a short description or abstract. Identify which hard problem(s) the publication addressed. Papers that have not yet been published should be reported in region 2 below.

P. Gao, H. Miao and J.S. Baras, “Social Network Ad Allocation via Hyperbolic Embedding,” Proceedings 53rd IEEE Conference on Decision and Control (IEEE CDC14), pp. 4875-4880, Los Angeles, CA, December 15-17, 2014. http://cps-vo.org/node/17117

Abstract:

With the increasing popularity and ubiquity of online social networks (SNS), many advertisers choose to post their advertisements (Ads) within SNS. As a central problem for Ad platforms, Ad allocation is to maximize its revenue without overcharging advertisers, and it has received increasing attention from both industry and academia. The offline approach is a high dimensional integer programming problem with constraints incorporating potential allocation requirements from advertisers. In this paper we investigate the SNS Ad allocation problem in a single target group setting, study the connection of SNS advertising and hyperbolic geometry, and propose an approximation using hyperbolic embedding, which not only reduces the dimensionality of SNS Ad allocation problem significantly, but also provides a general framework for designing allocation strategies incorporating business rules. We evaluate the optimality and efficiency of our approach.

S. Jain, T. Ta and J.S. Baras, “Physical Layer Methods for Privacy Provision in Distributed Control and Inference,” Proceedings 53rd IEEE Conference on Decision and Control (IEEE CDC14), pp. 1383-1388, Los Angeles, CA, December 15-17, 2014. http://cps-vo.org/node/17118

Abstract:

Distributed control, decision and inference schemes are ubiquitous in many current technological systems ranging from sensor networks, collaborative teams of humans and robots, and information retrieval systems. Privacy, both location and identity, is critical for many of these systems and applications. The principal thesis investigated in this paper is that the utilization of physical layer methods and implementation techniques substantially strengthens privacy in the associated algorithms and systems. In fact it is argued that without the utilization of such physical layer methods it may be expensive to have provable levels of security in these systems. We analyze the performance of such physical layer techniques. We then utilize these techniques to provide provable privacy in distributed control, decision and inference algorithms. We demonstrate the results in context of distributed Kalman filtering. We develop useful metrics to measure privacy in these distributed systems. We investigate quantitatively the effects of privacy loss on the performance of the systems.

Hard problems addressed: #2 (Policy-Governed Secure Collaboration);
#1 (Scalability and Composability); #5 (Understanding and Accounting for Human Behavior)

ACCOMPLISHMENT HIGHLIGHTS

Our goal is to develop a transformational framework for a science of trust, and its impact on local policies for collaboration, in networked multi-agent systems. The framework will take human behavior into account from the start by treating humans as integrated components of these networks, interacting dynamically with other elements. The new analytical framework will be integrated, and validated, with empirical methods of analyzing experimental data on trust, recommendation, and reputation, from several datasets available to us, in order to capture fundamental trends and patterns of human behavior, including trust and mistrust propagation, confidence in trust, phase transitions in the dynamic graph models involved in the new framework, stability or instability of collaborations. A key challenge addressed is the impact of the dynamics of trust and mistrust (or of positive and negative recommendations) on the capabilities of agents to collaborate and to execute tasks in a distributed manner.

The highlights of our results during this reporting quarter are as follows:

We developed new mathematical models for networks that carry opinions (beliefs) in their nodes, while the interaction between the nodes (agents) can be positive (friends) or negative (enemies). We analyzed the dynamics of belief evolution and emergence in such signed networks and discovered new laws governing these dynamics. Two types of models were considered regarding the negative interactions: state-flipping and relative-state flipping.

We developed a novel model and an efficient solution algorithm to the so called "Advertisement Allocation Problem" in large social networks, using a new and innovative embedding of the graph in hyperbolic space. The new algorithm obtains the same results as other algorithms albeit with complexity lower by two to four orders of magnitude.

We demonstrated how physical layer security schemes can be successfully employed to create a trusted core and provide privacy protection in distributed control and inference schemes in networked systems.

We investigated several problems in crowdsourcing, by developing novel methods and algorithms that can handle multiple domains of knowledge, multi-dimensional trust in the knowledge of people or experts, and budget constraints. We investigated analytically these problems and obtained new algorithms and results on their performance.

We developed novel trust-aware social recommender systems by interpreting connections in the social network as trust relationships among users and by establishing a trust network accordingly. Within the trust network, we propose models for trust and mistrust propagation and aggregation, and use them to design trust-aware recommendation algorithms with superior performance. We also investigated integration of our new schemes with classic collaborative filtering to take advantage of both approaches for better performance.

B) COMMUNITY INTERACTION

J.S. Baras gave the following invited, plenary and keynote lectures on the topics, approach and results in this Task:

(i) J.S. Baras, “Security and Trust in a Networked Immersed World: From Components to Systems and Beyond,” joint      invited distinguished lecture, Institute for Computer Science (ICS) of the Foundation for Research and Technology – Hellas (FORTH) and European Network and Information Security Agency (ENISA), Heraklion, Crete, Greece, September 17, 2014.