Trust, Recommendation Systems, and Collaboration - UMD - April 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

#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.

J.S. Baras, “A Fresh Look at Network Science: Interdependent Multigraphs Models Inspired From Statistical Physics,” invited paper, Proceedings of 6th International Symposium on Communications, Control and Signal Processing (ISCCSP 2014), Athens, Greece, May 21-23, 2014.

Abstract:

We consider several challenging problems in complex networks (communication, control, social, economic, biological, hybrid) as problems in cooperative multi-agent systems. We describe a general model for cooperative multi-agent systems that involves several interacting dynamic multigraphs and identify three fundamental research challenges underlying these systems from a network science perspective. We show that the framework of constrained coalitional network games captures in a fundamental way the basic tradeoff of benefits vs. cost of collaboration, in multi-agent systems, and demonstrate that it can explain network formation and the emergence or not of collaboration. Multi-metric problems in such networks are analyzed via a novel multiple partially ordered semirings approach. We investigate the interrelationship between the collaboration and communication multigraphs in cooperative swarms and the role of the communication topology, among the collaborating agents, in improving the performance of distributed task execution. Expander graphs emerge as efficient communication topologies for collaborative control. We relate these models and approaches to statistical physics.

X. Liu and J.S. Baras, “Using Trust in Distributed Consensus With Adversaries in Sensor and Other Networks,” invited paper, Proceedings of 17th International Conference on Information Fusion (FUSION 2014), Salamanca, Spain, July 7-10, 2014.  

Abstract:

Extensive research efforts have been devoted to distributed consensus with adversaries. Many diverse applications drive this increased interest in this area including distributed collaborative sensor networks, sensor fusion and distributed collaborative control. We consider the problem of detecting Byzantine adversaries in a network of agents with the goal of reaching consensus. We propose a novel trust model that establishes both local trust based on local evidences and global trust based on local exchange of local trust values. We describe a trustaware consensus algorithm that integrates the trust evaluation mechanism into the traditional consensus algorithm and propose various local decision rules based on local evidence. To further enhance the robustness of trust evaluation itself, we also provide a trust propagation scheme in order to take into account evidences of other nodes in the network. The algorithm is flexible and extensible to incorporate more complicated designs of decision rules and trust models. Then we show by simulation that the trust-aware consensus algorithm can effectively detect Byzantine adversaries and excluding them from consensus iterations even in sparse networks with connectivity less than 2f +1, where f is the number of adversaries. These results can be applied for fusion of trust evidences as well as for sensor fusion when malicious sensors are present like for example in power grid sensing and monitoring.

G. Shi, A. Proutiere, M. Johansson, J.S. Baras, and K. H. Johansson, “Emergent Behaviors over Signed Random Dynamical Networks: State-Flipping Model,”  IEEE Transactions on Control of Network Systems (IEEE TCNS), March 2015.

Abstract:

Recent studies from social, biological, and engineering network systems have drawn attention to the dynamics over signed networks, where each link is associated with a positive/negative sign indicating trustful/mistrustful, activator/inhibitor, or secure/malicious interactions. We study asymptotic dynamical patterns that emerge among a set of nodes that nteract in a dynamically evolving signed random network. Node interactions take place at random on a sequence of deterministic signed graphs. Each node receives positive or negative recommendations from its neighbors depending on the sign of the interaction arcs, and updates its state accordingly. Recommendations along a positive arc follow the standard consensus update. As in the work by Altafini, negative recommendations use an update where the sign of the neighbor state is flipped. Nodes may weight positive and negative recommendations differently, and random processes are introduced to model the time-varying attention that nodes pay to these recommendations. Conditions for almost sure onvergence and divergence of the node states are established. We show that under this so-called state-flipping model, all links contribute to a consensus of the absolute values of the nodes, even under switching sign patterns and dynamically changing environment. A no-survivor property is established, indicating that every node state diverges almost surely if the maximum network state diverges.

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.

P. Gao, J.S. Baras and J. Golbeck, “Trust Aware Social Recommender System Design,” Proceedings 2015 International Conference on Information Systems Security and Privacy (ICISSP 2015), INSTICC, pp. 19-28, February 9-11, 2015, Angers, France.

Abstract:

In this work, we develop a trust-aware recommender system. We interpret connections in associated social graph as trust relationships among users in the recommender system, and establish a trust network accordingly. Within the trust network, we propose models for trust propagation and aggregation, and design trust-aware recommendation algorithms to predict the preferences of users over items (services). Specially, we handle indirect trust in our model, which could enlarge the information source to a large amount. We also discuss the issue of distrust (i.e. negative trust, negative opinion) and propose a way to consider both trust (positive opinion) and distrust in our model. We also consider integrating our trust-aware recommendation framework with classic collaborative filtering to take advantage of both approaches and further improve the performance in rating estimation and item recommendation. As an example of application scenario, such framework of trust-aware recommender system design can be applied for directed SNS like Epinions and Delicious. Currently we are at the stage of evaluating the accuracy and efficiency of the system with both synthetic and real data. Meanwhile, we are trying to extend our model to further improve its performance.

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, during the past year of research in this task:

(i) J.S. Baras, “Trust in Networks and Networked Systems,” invited distinguished lecture, TRUST center, University of California Berkeley, Berkeley, CA, March 6, 2014.

(ii) J.S. Baras, “Hyperbolic Embedding to the Rescue in Communication and Social Networks, invited distinguished lecture, Digital Technology Center, College of Science and Engineering, University of Minnesota, Minneapolis, MN, April 23, 2014.

(iii) J.S. Baras, “Networked CPS: Some Fundamental Challenges,” invited position statement in the invited Panel on “Networking Challenges for Cyber-Physical Systems”, 2014 IEEE INFOCOM, Toronto, Canada, April 27 - May 2, 2014.

(iv) J.S. Baras, “Hyperbolic Embedding in Communication and Social Networks,” invited distinguished lecture, Computer Engineering and Telecommunications Department, University of Thessaly, Volos, Greece, May 13, 2014.

(v) J.S. Baras, “Security and Trust in a Networked Immersed World: From Components to Systems and Beyond,” invited keynote lecture, Workshop on Security and Safety: Issues, Concepts and Ideas , 2nd Hellenic Forum for Science, Innovation and Technology, Demokritos Research Center, Athens, Greece, June 30 - July 4, 2014.

(vi) 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.