(最具CSUR 2016：综述) Understanding Graph-Based Trust Evaluation in Online Social Networks Methodologies and Challenges

Trust

Abstract

The implement of evaluation ratepaying credit grade needs the result of analyzing and judging lots of taxation data, and decision tree is the one of the common tools for data mining and classification, especially C4.5, is a kind of classification algorithm. How to apply data mining technology to change the phenomenon, that evaluation ratepaying credit grade by manualoperation, is one of the difficult points of today' s tax system taxation informatization work. The maintopic of this treatise is discussing how to build a ratepaying credit grade decision tree with C4.5 algorithm, finally build it through a serious of processes, such as gathering, preprocessing, attribute choosing, decision tree generating and pruning, and judge the taxation credit grade by the generated decision tree.

1 Introduction

1.0 The importance of Trust

• As we know, trust is the basis of almost all online interactions. Without trust, people cannot cooperate well with others, and the online system cannot run smoothly.

1.1 The Typical Properties of Trust

• Subjective: Trust is subjective since “trust in a person” is a kind of opinion from a specific user. In particular, how can we collect evidence to estimate people’s trust in others, given that people usually do not express their trust opinions frankly due to concerns like worsening a relation with someone. It is even more challenging to consider how we can integrate incomplete and inaccurate evidence to make an accurate prediction.
• Asymmetric: Trust is asymmetric, which indicates that the degree to which A trusts B is usually not equal to that of Btrusting A.
• Time-sensitive: trust is time-sensitive because trust is a type of human relation. As time passes, some old relations may weaken, while some new relations can be built. In addition, people’s opinions may vary with time, which also leads to changes in trust.

1.2 The Properties of Computation Trust

• Propagative: trust relations can be diffused along a chain. "weak-transitive" or "nontransitive"
• Composable: the trust values induced from multiple trusted paths can be integrated as one value. Composing several trusted paths is quite difficult, especially when different paths provide contradictory information.

1.3 Closely Related Concepts

• (social) influence: the tool that makes user interactions happen.
• recommendation: the method that allows opinions to propagate.

2 Related Work

2.1. Existing Surveys on Trust

2.2 Trust Models in Methodologies

• D-S evidence theory and subjective logic-based approaches
• Approaches using traditional mathematics tools (probability statistics,
  fuzzy logic, etc.)
• AI and information theory-based approaches
• Graph-based approaches

2.3 Researches on Recommendation and Influence

2.4 Trust-Related Systems and Applications

3 Graph Simplification-based Approach

3.1 Representative Models

3.2 Challenge: Path Length Limitation & Evidence Availability

• Graph simplification-based approaches use both the propagative and composable properties of computation trust.
  
  • Propagative： It faces the challenge of setting a proper limitation of path length; a smaller limitation may lead to fewer paths, whereas a larger one may cause inaccurate prediction.
  • Composable：For multiple trusted paths in a trusted graph, how to combine the available evidence is the main challenge.
• However, to the best of our knowledge, there is still no conclusion about the best trusted path length and the most proper number of paths, even in a specific context.
• The challenge is still open and worth further attention. Nevertheless, the problem is context-dependent, and the key is to find a balance between path length [Kim and Song 2011] and evidence availability [Cho et al. 2012]. (The balance of trust availability and path reliability)

4 Graph Analogy-based Approach

4.1 Representative Models

4.2 Challenges: Normalization and Scalability

• Normalization: Graph analogy-based models may produce a result that is out of the range of trust. Then, proper normalization will have to be done. For a general graph analogy-based model, how to design a reasonable normalization algorithm is a big challenge.
• Scalability: In general, when using a graph analogy-based model, the network scale should not be large because of the time and space complexity.
• We believe that a better way is to combine the graph simplification- and graph analogy-based approaches: first, use simplification to generate a small trusted graph; then, conduct a graph analogy trust evaluation.

5 Common Challenges

5.1 Path Dependence

• Researchers have taken some action to address the challenge of path dependence. However, there is still no universally accepted solution. Existing work may ignore or reuse some information on the shared edges.
  
  • uses only the shortest, strongest paths and neglects all others
  • take each path as an independent path, which reuses the information on the shared edges
• Trust evidence is one of the key factors of trust evaluation. Thus, a comprehensive trust model is expected to treat trust evidence properly. Based on our experience, either evidence ignorance or reuse may lead to inaccurate results for trust evaluation.

5.2 Trust Decay

• Decay with time: Due to the time sensitivity of trust, it may change (usually decay) with time. Time should be an essential factor of a comprehensive trust model
• Decay with space: Trust may decay via iterative recommendations because people put more trust in friends than in strangers. The length of a trusted path cannot be too long.

5.3 Opinion Conflict

• conflict of opinions or controversiality of the target: Due to the subjectivity of trust, people may have different opinions toward the same target: Some may give high opinions, while others give low ones. Then, how to combine different opinions becomes a big challenge.
  
  • taking those paths whose trust levels are above a predefined threshold or taking the most reliable paths and neglecting others, which may cause information loss
  • taking the weighted average or the most reliable path to gain a final opinion
• Based on several prior studies, we suggest that efforts in solving opinion conflict in trust evaluation can be made from two main aspects:
  
  • One is to fully understand the personal bias and features of the trustor;
  • the other is to deeply explore the fundamental principles regarding the formulation and evolution of people’s opinions.

5.4 Attack Resistance

• the trust system itself may be attacked either by malicious or selfish users. In OSNs, users may conduct several kinds of misbehavior, such as providing bad service , sybil attack, bad-mouthing, on-off attack, conflicting behavior attack, and social spamming. Then, how to make a trust model resistant to possible attacks is a more serious challenge.
• A combination of trust and security models may be expected. An attack-resistant trust model should be able to punish malicious behaviors and provide more incentive techniques to encourage user cooperation.

6 Pre- And Postprocess

6.1 Information Collection for Trust

• trust is commonly taken as being subjective and personal; trust can also be specific or general.
• Information collected for forming trust can be either one- or multidimensional.
• Trust can be represented by a scalar number. It can be continuous and normalized to the range [0, 1]; it can also be binary (0 or 1 in Epinions) or have discrete levels (e.g., [1, 5] in Amazon).

6.2 Trusted Graph Construction

• path selection
• component induction

6.3 Model Evaluation

• Evaluation Method
  
  • using feedback by simulation
  • using the leave-one-out method
• Evaluation Metrics
  
  • Coverage
  • Mean Absolute Error $(MAE)$
  • Root Mean Squared Error $(RMSE)^2$
  • Precision
  • Recall
  • FScore
• Dataset
  
  • trust
  • Epinions
  • FilmTrust