11institutetext: Jožef Stefan Institute, Jamova 39, 1000 Ljubljana, Slovenia
22institutetext: Jožef Stefan Int. Postgraduate School, Jamova 39, 1000
Ljubljana, Slovenia 33institutetext: University of Ljubljana, Faculty of
Computer and Information Science, Večna pot 113, Ljubljana, Slovenia
33email<EMAIL_ADDRESS>
# Identification of COVID-19 related Fake News via Neural Stacking

Boshko Koloski 1122 Timen Stepišnik-Perdih 33 Senja Pollak 11
Blaž Škrlj 1122

###### Abstract

Identification of Fake News plays a prominent role in the ongoing pandemic,
impacting multiple aspects of day-to-day life. In this work we present a
solution to the shared task titled COVID19 Fake News Detection in English,
scoring the 50th place amongst 168 submissions. The solution was within 1.5%
of the best performing solution. The proposed solution employs a heterogeneous
representation ensemble, adapted for the classification task via an additional
neural classification head comprised of multiple hidden layers. The paper
consists of detailed ablation studies further displaying the proposed method’s
behavior and possible implications. The solution is freely available.
https://gitlab.com/boshko.koloski/covid19-fake-news

###### Keywords:

Fake-news detection Stacking ensembles Representation learning.

Please cite the original version, with the following doi:
10.1007/978-3-030-73696-5_17 (at CONSTRAINT 2021: Combating Online Hostile
Posts in Regional Languages during Emergency Situation pp. 177-188) and is
available online at
https://link.springer.com/chapter/10.1007/978-3-030-73696-5_17.

##  1 Introduction

Fake news can have devastating impact on the society. In the times of a
pandemic, each piece of information can have a significant role in the lives
of everyone. The verification of the truthfulness of a given information as a
fake or real is crucial, and can be to some extent learned [10]. Computers, in
order to be able to solve this task, need the data represented in a numeric
format in order to draw patterns and decisions. We propose a solution to this
problem by employing various natural language processing and learning
techniques.

The remainder of this work is structured as follows: Section 2 describes the
prior work in the field of detection of fake-news. The provided data is
described in Section 3 and Section 4 explains our proposed problem
representation approaches while Section 5 introduces two different meta-models
built on top of the basic representations listed in Section 4. The experiments
and results achieved are listed in Section 6, finally the conclusion and the
proposed future work are listed in Section 7.

##  2 Related Work

The fake-news text classification task [16] is defined as follows: given a
text and a set of possible classes fake and real, to which a text can belong,
an algorithm is asked to predict the correct class of the text. Most
frequently, fake-news text classification refers to classification of data
from social media. The early proposed solutions to this problem used hand
crafted features of the authors such as word and character feature
distributions. Interactions between fake and real news spread on social media
gave the problem of fake-news detection a network-alike nature[18]. The
network based modeling discovered useful components of the fake-news spreading
mechanism and led to the idea of the detection of bot accounts [17].

Most of the current state-of-the-art approaches for text classification
leverage large pre-trained models like the one Devlin et al. [1] and have
promising results for detection of fake news [4]. However for fake-news
identification tasks, approaches that make use of n-grams and the Latent
Semantic Analysis [2] proved to provide successful solutions on this task (see
Koloski et al. [5]). Further enrichment of text representations with
taxonomies and knowledge graphs[19] promises improvements in performance.

##  3 Data description

In this paper we present a solution to the subset of the fake-news detection
problem - The identification of COVID-19 related Fake News [11, 10]. The
dataset consists of social media posts in English collected from Facebook,
Twitter and Instagram, and the task is to determine for a given post if it was
real or fake in relation to COVID-19. The provided dataset is split in three
parts: train, validation and test data. The distribution of data in each of
the data sets is shown in Table 1.

Table 1: Distribution of the labels in all of the data splits. part | train | validation | test
---|---|---|---
size | 6420 | 2140 | 2140
real | 3360(52%) | 1120(52%) | 1120(52%)
fake | 3060(48%) | 1020(48%) | 1020(48%)

##  4 Proposed method

The proposed method consists of multiple submethods that aim to tackle
different aspects of the problem. On one side we focus on learning the hand
crafted features of authors and on the other we focus on learning the
representation of the problem space with different methods.

###  4.1 Hand crafted features

####  4.1.1 Word based

Maximum and minimum word length in a tweet, average word length, standard
deviation of the word length in tweet. Additionally we counted the number of
words beginning with upper and the number of words beginning a lower case.

####  4.1.2 Char based

The character based features consisted of the counts of digits, letters,
spaces, punctuation, hashtags and each vowel, respectively.

###  4.2 Latent Semantic Analysis

Similarly to Koloski et al. [5] solution to the PAN2020-Fake News profiling we
applied the low dimensional space estimation technique. First we preprocessed
the data by lower-casing the tweet content and removing the hashtags and
punctuation. After that we removed the stopwords and obtained the final clean
presentation. From the cleaned text, we generated the POS-tags using the NLTK
library[6].

Figure 1: Text preparation for the LSA.

For the feature construction space we used the technique used by Martinc et
al. [8] which iteratievly weights and chooses the best n-grams. We used two
types of n-grams:

  * •

Word based: n-grams of size 1 and 2

  * •

Character based: n-grams of size 1, 2 and 3

We generated $n$ features with $n/2$ of them being word and $n/2$ character
n-grams. We calculated TF-IDF on them and preformed SVD [3] With the last step
we obtained the LSA representation of the tweets.

For choosing the optimal number of features n and number of dimensions d, we
created custom grid consisted of $n`\in[500,1250,2500,5000,10000,15000,20000]$
and $d`\in[64,128,256,512,768]$. For each tuple $(n`,d`),n`\in$ d and $d`\in$
d we generated a representation and trained (SciKit library [12]) SVM and a LR
(Logistic regression) classifier. The learning procedure is shown in Figure 2.

Figure 2: The proposed learning procedure with the LSA. The evaluation is
performed on validation dataset.

The best performing model had $2500$ features reduced to $512$ dimensions.

###  4.3 Contextual features

We explored two different contextual feature embedding methods that rely on
the transformer architecture. The first method uses the already pretrained
sentence_transfomers and embedds the texts in an unsupervised manner. The
second method uses DistilBERT which we fine tune to our specific task.

####  4.3.1 sentence_transfomers

For fast document embedding we used three different contextual embedding
methods from the sentence_transfomers library [14]:

  * •

distilbert-base-nli-mean-tokens

  * •

roberta-large-nli-stsb-mean-tokens

  * •

xlm-r-large-en-ko-nli-ststb

First, we applied the same preprocessing as shown in Figure 1, where we only
excluded the POS tagging step. After we obtained the preprocessed texts we
embedded every tweet with a given model and obtained the vector
representation. After we obtained each representation, we learned a Stochastic
Gradient Descent based learner, penalizing both the ”linear” and ”hinge” loss
parameters. The parameters were optimized on a GridSearch with a 10-fold
Cross-validation on every tuple of parameters.

####  4.3.2 DistilBERT

is a distilled version of BERT that retains best practices for training BERT
models [15]. It is trained on a concatenation of English Wikipedia and Toronto
Book Corpus. To produce even better results, we fine-tuned the model on train
data provided by the organizers. BERT has its own text tokenizer and is not
compatible with other tokenizers so that is what we used to prepare data for
training and classification.

###  4.4 tax2vec features

tax2vec [19] is a data enrichment approach that constructs semantic features
useful for learning. It leverages background knowledge in the form of taxonomy
or knowledge graph and incorporates it into textual data. We added generated
semantic features using one of the two approaches described below to top 10000
word features according to the TF-IDF measure. We then trained a number of
classifiers on this set of enriched features (Gradient boosting, Random
forest, Logistic regression and Stochastic gradient descent) and chose the
best one according to the F1-score calculated on the validation set.. Taxonomy
based (tax2vec).  Words from documents are mapped to terms of the WordNet
taxonomy [13], creating a document-specific taxonomy after which a term-
weighting scheme is used for feature construction. Next, a feature selection
approach is used to reduce the number of features. Knowledge Graph based
(tax2vec(kg)).  Nouns in sentences are extracted with SpaCy and generalized
using the Microsoft Concept Graph [9] by ”is_a” concept. A feature selection
approach is used to reduce the number of features.

##  5 Meta models

From the base models listed in Section 4 we constructed two additional meta-
models by combining the previously discussed models.

###  5.1 Neural stacking

In this approach we learn a dense representation with 5-layer deep neural
network. For the inputs we use the following representations:

  * •

LSA representation with $N=2500$ features reduced to $d=256$ dimensions.

  * •

Hand crafted features - $d=16$ dimensions

  * •

distilbert-base-nli-mean-tokens \- $d=768$ dimensions

  * •

roberta-large-nli-stsb-mean-tokens \- $d=768$ dimensions

  * •

xlm-r-large-en-ko-nli-ststb \- $d=768$ dimensions

This represents the final input $X_{Nx2576}$ for the neural network. After
concatenating the representations we normalized them. We constructed a custom
grid consisted of learning_rate = $\lambda\in$ [0.0001, 0.005, 0.001, 0.005,
0.01, 0.05, 0.1], dropout = $p\in$ [0.1, 0.3, 0.5, 0.7], batch_size $\in$
[16,32,64,128,256], epochs $\in$ [10, 100, 1000]. In the best configuration we
used the SELU activation function and dropout $p=0.7$ and learning rate
$\lambda=0.001$. The loss function was Cross-Entropy optimized with the
$StochasticGradientOptimizer$, trained on $epochs=100$ and with
$batch\\_size=32$.
Layers were composed as following:

  * •

input layer - $d=2576$ nodes

  * •

$dense_{1}$ layer - $d=896$ nodes, activation = SELU

  * •

$dense_{2}$ layer - $d=640$ nodes, activation = SELU

  * •

$dense_{3}$ layer - $d=512$ nodes, activation = SELU

  * •

$dense_{4}$ layer - $d=216$ nodes, activation = SELU

  * •

$dense_{5}$ layer - $d=2$ nodes, activation = Sigmoid

###  5.2 Linear stacking

The second approach for meta-learning considered the use of the predictions
via simpler models as the input space. We tried two separate methods:

####  5.2.1 Final predictions

We considered the predictions from the LSA, DistilBert, dbert, xlm, roberta,
tax2vec as the input. From the models’ outputs we learned a Stochastic
Gradient Optimizer on 10-fold CV. The learning configuration is shown in
Figure 3.

Figure 3: Stacking architecture based on base model predictions.

####  5.2.2 Decision function-based prediction

In this approach we took the given classifier’s value of the decision function
as the input in the stacking vector. For the SVM based SGD we used the
decision_function and for the Logistic Regression we used the
Sidmoid_activation. The proposed architecture is similar to the architecture
in Figure 3, where prediction values are replaced by decision function values.

##  6 Experiments and results

This section describes model parameters, our experiments and the results of
experiments as well as the results of the final submission.

We conducted the experiments in two phases. The experiment phases synced with
the competition phases and were defined as TDT phase and CV phase. In the TDT
phase the train and validation data is split into three subsets, while in the
CV phase all data is concatenated and evaluated on 10-folds.

Table 2: Final chosen parameters for the best model of each vectorization.

Vectorization | Model | Parameters
---|---|---
LSA | LR | ’l1_ratio’: 0.05, ’penalty’: ’elasticnet’, ’power_t’: 0.5
Hand crafted features | SVM | ’l1_ratio’: 0.95, ’penalty’: ’elasticnet’, ’power_t’: 0.1
distilbert-base-nli-mean-tokens | LR | ’C’: 0.1, ’penalty’:’l2’
roberta-large-nli-stsb-mean-tokens | LR | ’C’:’0.01’, ’penalty’: ’l2’
xlm-r-large-en-ko-nli-ststb | SVM | ’C’: 0.1, ’penalty’: ’l2’
linear stacking_probs | SGD | ’l1_ratio’: 0.8, ’loss’: ’hinge’, ’penalty’: ’elasticnet’
linear stacking | SGD | ’l1_ratio’: 0.3, ’loss’: ’hinge’, ’penalty’: ’elasticnet’
tax2vec_tfidf | SGD | ’alpha’: 0.0001, ’l1_ratio’: 0.15, ’loss’: ’hinge’, ’power_t’: 0.5
tax2vec(kg)_tfidf | SVM | ’C’: 1.0, ’kernel’: ’rbf’

###  6.1 Train-development-test (TDT) split

In the first phase, we concatenated the train and the validation data and
splitted it into three subsets: train(75%), dev(18.75%) and test(6.25%). On
the train split we learned the classifier which we validated on the dev set
with measurement of F1-score. Best performing model on the dev set was finally
evaluated on the test set. Achieved performance is presented in Table 3 and
the best performances are shown in Figure 4.

Table 3: F1-scores for different methods of vectorization on the TDT data
split.

Vectorization | Train F1-score | DEV F1-score | Test F1-score
---|---|---|---
distilBERT-tokenizer | 0.9933 | 0.9807 | 0.9708
neural stacking | 0.9645 | 0.9377 | 0.9461
linear stacking | 0.9695 | 0.9445 | 0.9425
tax2vec | 0.9895 | 0.9415 | 0.9407
linear stacking_probs | 0.9710 | 0.9380 | 0.9390
LSA | 0.9658 | 0.9302 | 0.9281
roberta-large-nli-stsb-mean-tokens | 0.9623 | 0.9184 | 0.9142
xlm-r-large-en-ko-nli-ststb | 0.9376 | 0.9226 | 0.9124
distilbert-base-nli-mean-tokens | 0.9365 | 0.9124 | 0.9113
tax2vec(kg) | 0.8830 | 0.8842 | 0.8892
Hand crafted features | 0.7861 | 0.7903 | 0.7805

DistilBERT comes out on top in F1-score evaluation on all data sets in TDT
data split—to the extent that we feared overfitting on the train data—while
handcrafting features did not prove to be successful. Taxonomy based tax2vec
feature construction trails distilBERTs score but using a knowledge graph to
generalize constructed features seemed to decrease performance significantly
(tax2vec(kg)). Other methods scored well, giving us plenty of reasonably good
approaches to consider for the CV phase.

Figure 4: Best performing methods of feature vectorization according to
F1-score.

###  6.2 CV split

In the second phase - the CV phase we concatenated the data provided by the
organizers and trained models on 10-fold Cross-Validation. The evaluation of
the best-performing models is presented in Table 4.

During cross-validation, LSA showed consistency in good performance. With
similar performance were the tax2vec methods which this time scored very
similarly.

Table 4: F1-scores of models when training using 10-fold cross-validation. Model name | Vectorization | 10-fold CV
---|---|---
LSA | LSA | 0.9436
sentence_transformers | distilbert | 0.9071
sentence_transformers | roberta-large | 0.9077
sentence_transformers | xlm-roberta | 0.9123
gradient boosting | tax2vec | 0.9335
gradient boosting | tax2vec(kg) | 0.9350

###  6.3 Evaluating word features

To better understand the dataset and trained models we evaluated word features
with different metrics to pinpoint features with the highest contribution to
classification or highest variance.

####  6.3.1 Features with the highest variance

We evaluated word features within the train dataset based on variance in
_fake_ and _real_ classes and found the following features to have the highest
variance:

_”Fake” class_ • cure  • coronavirus  • video  • president  • covid  • vaccine
• trump  • 19

_”Real” class_ • number  • total  • new  • tests  • deaths  • states  •
confirmed  • cases  • reported

####  6.3.2 SHAP extracted features

After training the models we also used Shapley Additive Explanations [7] to
extract the most important word features for classification into each class.
The following are results for the gradient boosting model:

_”Fake” class_ • video  • today  • year  • deployment  • trump  • hypertext
transfer protocol

_”Real” class_ • https  • covid19  • invoking  • laboratories  • cases  •
coronavirus

####  6.3.3 Generalized features

We then used WordNet with a generalizing approach called ReEx (Reasoning with
Explanations)111https://github.com/OpaqueRelease/ReEx to generalize the terms
via the “is_a” relation into the following terms:

_”Fake” class_ • visual communication  • act  • matter  • relation  • measure
• hypertext transfer protocol  • attribute

_”Real” class_ • physical entity  • message  • raise  • psychological feature

###  6.4 Results

Results of the final submissions are shown in Table 5.

Table 5: Final submissions F1-score results. submission name | model | F1-score
---|---|---
btb_e8_4 | neural stacking | 0.9720
btb_e8_3 | LSA | 0.9416
btb_e8_1 | tax2vec | 0.9219
btb_e8_2 | linear stacking | 0.8464
btb_e8_5 | distilbert | 0.5059

DistilBERT appears to have overfitted the train data on which it achieved very
high F1-scores, but failed to perform well on the test data in the final
submission. Our stacking method also failed to achieve high results in the
final submission, being prone to predict “fake” news as can be seen in Figure
5. On the other hand, the taxonomy based tax2vec data enrichment method as
well as the LSA model have both shown good results in the final submission,
while our best performing model used stacking, where we merged different
neural and non-neural feature sets into a novel representation. With this
merged model, we achieved 0.972 F1-score and ranked 50th out of 168
submissions.

In Figure 5 we present the confusion matrices of the models evaluated in the
final submissions.

|  |
---|---|---
|  |
Figure 5: Heatmaps of predicted and actual labels on final submission results.

##  7 Conclusion and further work

In our take to tackle the detection of fake-news problems we have have
exploited different approaches and techniques. We constructed hand crafted
features that captured the statistical distribution of words and characters
across the tweets. From the collection of n-grams of both character and word-
based features to be found in the tweets we learned a latent space
representation, potentially capturing relevant patterns. With the employment
of multiple BERT-based representations we captured the contextual information
and the differences between fake and real COVID-19 news. However such learning
showed that even though it can have excellent results for other tasks, for
tasks such as classification of short texts it proved to fall behind some more
sophisticated methods. To overcome such pitfalls we constructed two different
meta models, learned from the decisions of simpler models. The second model
learned a new space from the document space representations of the simpler
models by embedding it via a 5 layer neural network. This new space resulted
in a very convincing representation of this problem space achieving F1-score
of 0.9720 on the final (hidden) test set.

For the further work we suggest improvements of our methods by the inclusion
of background knowledge to the representations in order to gain more instance
separable representations. We propose exploring the possibility of adding
model interpretability with some attention based mechanism. Finally, as
another add-on we would like to explore how the interactions in the networks
of fake-news affect our proposed model representation.

##  8 Acknowledgements

The work of the last author was funded by the Slovenian Research Agency (ARRS)
through a young researcher grant. The work of other authors was supported by
the Slovenian Research Agency core research programme _Knowledge Technologies_
(P2-0103) and the ARRS funded research projects _Semantic Data Mining for
Linked Open Data (ERC Complementary Scheme, N2-0078)_ and _Computer-assisted
multilingual news discourse analysis with contextual embeddings - J6-2581)_ .
The work was also supported by European Union’s Horizon 2020 research and
innovation programme under grant agreement No 825153, project EMBEDDIA (Cross-
Lingual Embeddings for Less-Represented Languages in European News Media).

## References

  * [1] Devlin, J., Chang, M.W., Lee, K., Toutanova, K.: Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810.04805 (2018)
  * [2] Dumais, S.T.: Latent semantic analysis. Annual Review of Information Science and Technology 38(1), 188–230 (2004). https://doi.org/https://doi.org/10.1002/aris.1440380105, https://asistdl.onlinelibrary.wiley.com/doi/abs/10.1002/aris.1440380105
  * [3] Halko, N., Martinsson, P.G., Tropp, J.A.: Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions (2009)
  * [4] Jwa, H., Oh, D., Park, K., Kang, J.M., Lim, H.: exbake: Automatic fake news detection model based on bidirectional encoder representations from transformers (bert). Applied Sciences 9(19), 4062 (2019)
  * [5] Koloski, B., Pollak, S., Škrlj, B.: Multilingual detection of fake news spreaders via sparse matrix factorization. In: CLEF (2020)
  * [6] Loper, E., Bird, S.: Nltk: The natural language toolkit. In: Proceedings of the ACL-02 Workshop on Effective Tools and Methodologies for Teaching Natural Language Processing and Computational Linguistics - Volume 1. p. 63–70. ETMTNLP ’02, Association for Computational Linguistics, USA (2002). https://doi.org/10.3115/1118108.1118117, https://doi.org/10.3115/1118108.1118117
  * [7] Lundberg, S.M., Lee, S.I.: A unified approach to interpreting model predictions. In: Guyon, I., Luxburg, U.V., Bengio, S., Wallach, H., Fergus, R., Vishwanathan, S., Garnett, R. (eds.) Advances in Neural Information Processing Systems 30, pp. 4765–4774. Curran Associates, Inc. (2017), http://papers.nips.cc/paper/7062-a-unified-approach-to-interpreting-model-predictions.pdf
  * [8] Martinc, M., Skrlj, B., Pollak, S.: Multilingual gender classification with multi-view deep learning: Notebook for PAN at CLEF 2018. In: Cappellato, L., Ferro, N., Nie, J., Soulier, L. (eds.) Working Notes of CLEF 2018 - Conference and Labs of the Evaluation Forum, Avignon, France, September 10-14, 2018. CEUR Workshop Proceedings, vol. 2125. CEUR-WS.org (2018), http://ceur-ws.org/Vol-2125/paper_156.pdf
  * [9] Nsl, D.I.: Microsoft concept graph: Mining semantic concepts for short text understanding 1, 262–294 (11 2019)
  * [10] Patwa, P., Bhardwaj, M., Guptha, V., Kumari, G., Sharma, S., PYKL, S., Das, A., Ekbal, A., Akhtar, M.S., Chakraborty, T.: Overview of constraint 2021 shared tasks: Detecting english covid-19 fake news and hindi hostile posts. In: Proceedings of the First Workshop on Combating Online Hostile Posts in Regional Languages during Emergency Situation (CONSTRAINT). Springer (2021)
  * [11] Patwa, P., Sharma, S., PYKL, S., Guptha, V., Kumari, G., Akhtar, M.S., Ekbal, A., Das, A., Chakraborty, T.: Fighting an infodemic: Covid-19 fake news dataset. arXiv preprint arXiv:2011.03327 (2020)
  * [12] Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P., Weiss, R., Dubourg, V., Vanderplas, J., Passos, A., Cournapeau, D., Brucher, M., Perrot, M., Duchesnay, E.: Scikit-learn: Machine learning in Python. Journal of Machine Learning Research 12, 2825–2830 (2011)
  * [13] Princeton University: About wordnet. (2010)
  * [14] Reimers, N., Gurevych, I.: Sentence-bert: Sentence embeddings using siamese bert-networks. In: Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing. Association for Computational Linguistics (11 2019), https://arxiv.org/abs/1908.10084
  * [15] Sanh, V., Debut, L., Chaumond, J., Wolf, T.: Distilbert, a distilled version of bert: smaller, faster, cheaper and lighter. CoRR 1910.01108 (2019)
  * [16] Shannon, P., Markiel, A., Ozier, O., Baliga, N.S., Wang, J.T., Ramage, D., Amin, N., Schwikowski, B., Ideker, T.: Cytoscape: a software environment for integrated models of biomolecular interaction networks. Genome research 13(11), 2498–2504 (2003)
  * [17] Shao, C., Ciampaglia, G.L., Varol, O., Yang, K.C., Flammini, A., Menczer, F.: The spread of low-credibility content by social bots. Nature communications 9(1), 1–9 (2018)
  * [18] Shu, K., Bernard, H.R., Liu, H.: Studying fake news via network analysis: detection and mitigation. In: Emerging Research Challenges and Opportunities in Computational Social Network Analysis and Mining, pp. 43–65. Springer (2019)
  * [19] Škrlj, B., Martinc, M., Kralj, J., Lavrač, N., Pollak, S.: tax2vec: Constructing interpretable features from taxonomies for short text classification. Computer Speech & Language p. 101104 (2020). https://doi.org/https://doi.org/10.1016/j.csl.2020.101104, http://www.sciencedirect.com/science/article/pii/S0885230820300371


# Survey on social reputation mechanisms: Someone told me I can trust you

— student project —

Thomas Werthenbach  Delft University of TechnologyDelftThe Netherlands
<EMAIL_ADDRESS>and  Johan Pouwelse  Delft University of
TechnologyDelftThe Netherlands<EMAIL_ADDRESS>
###### Abstract.

Nowadays, most business and social interactions have moved to the internet,
highlighting the relevance of creating online trust. One way to obtain a
measure of trust is through reputation mechanisms, which record one’s past
performance and interactions to generate a reputational value. We observe that
numerous existing reputation mechanisms share similarities with actual social
phenomena; we call such mechanisms ‘social reputation mechanisms’. The aim of
this paper is to discuss several social phenomena and map these to existing
social reputation mechanisms in a variety of scopes. First, we focus on
reputation mechanisms in the individual scope, in which everyone is
responsible for their own reputation. Subjective reputational values may be
communicated to different entities in the form of recommendations. Secondly,
we discuss social reputation mechanisms in the acquaintances scope, where
one’s reputation can be tied to another through vouching or invite-only
networks. Finally, we present existing social reputation mechanisms in the
neighbourhood scope. In such systems, one’s reputation can heavily be affected
by the behaviour of others in their neighbourhood or social group.

††copyright: none

##  1\. Introduction

Nowadays, most business and social interactions have moved to the internet,
highlighting the relevance of creating online trust. The COVID-19 pandemic has
shown that, in time of crises, the online news and social media usage
increases (Van Aelst et al., 2021), increasing the risk and impact of
misinformation. As such, it is commonly known that governments have attempted
to control news media to spread propaganda in the past. Additionally, research
shows that individuals getting their news from social media are often more
likely to belief conspiracy theories (Enders et al., 2021). Such matters raise
the relevant and contemporary question: who to trust?

In an automated setting, the trust measure is often extracted from one’s
reputation. Their reputation may be calculated through the amount of ‘good’
work one has performed, or the reputation of their direct peers. We call
systems performing such calculations reputation mechanisms. Many reputation
mechanisms have been proposed and evaluated (Wang et al., 2010; Page et al.,
1999; Nasrulin et al., 2022; Xie et al., 2012; Kellett et al., 2011; Chen et
al., 2015; Tian et al., 2006; Zhang et al., 2009). The core components of
reputation mechanisms may vary greatly, e.g. it may assume that entities have
a fixed initial identity or that some entity $i$ sending some entity $j$ a
message provides a proof of personhood for entity $j$. However, the common
purpose of reputation mechanisms is to provide some measure of benevolence or
trustworthiness.

The overall scope of this paper is focused on social reputation mechanisms.
Such reputation mechanisms are a virtual reflection of genuine social
phenomena, such as vouching or familial relationships. We provide a survey in
which we have rigorously reviewed social reputation mechanisms by exploring
various social concepts and mapping these to existing reputation mechanisms.

Through the course of this paper, we gradually increase our scope and consider
social reputation mechanisms based on social phenomena on an increasingly
larger scale. First, we discuss the individual level. In this scope, no two
persons necessarily know each other initially and everyone’s reputation is
based solely on the work they perform or the quality they provide. Secondly,
we consider one’s acquaintances. Existing social ties and vouching are
concepts which may transpire in this space. Lastly, we discuss phenomena
occurring in one’s direct neighbourhood. For instance, the neighbourhood in
which you live may affect your reputation to both members outside and inside
that neighbourhood.

First, we provide more background on the importance and relevance of creating
trust and reputation mechanisms in section 2. Section 3 provides formal
definitions and data structures, which we use to generalise the mathematical
foundations of reviewed mechanisms in order to reduce the usage of varying
mathematical models across the different reputation mechanisms. Section 4
considers entities individually, and rigorously discusses different reputation
mechanisms based on social phenomena within this scope. Section 5 continues
exploring social concepts in the acquaintances scope and their associated
social reputation mechanisms. The last scope, neighbourhoods, is discussed in
section 6. A brief overview of all discussed social reputation mechanisms can
be found in Table 1.

Table 1.  Overview of all social reputation mechanisms reviewed in this paper, as well as associated work. Year |  Mechanism |  Reputation model |  Related
---|---|---|---
1999 |  PageRank (Page et al., 1999). Type: individual. Assumes important websites are likely linked to from other websites. Links are quantified iteratively until stationary state. |  $R_{i}=c\sum_{v\in B_{i}}\frac{R_{i}}{|N_{i}|}$ |  (Zhang et al., 2017; Bi et al., 2008; Wang et al., 2008; Pujol et al., 2002)
2006 |  GroupRep (Tian et al., 2006). Type: neighbourhood. Users form natural groups. The group reputation is assumed when there has not been sufficient direct interaction. |  Given utility $u_{ij}$ and cost $c_{ij}$ from $i$ to $j$:
$R_{ij}=\frac{\sum c_{ij}-u_{ij}}{\sum c_{ij}+u_{ij}}$ |  (Sabater and Sierra, 2001; Wu et al., 2009; Sun et al., 2005; Ji et al., 2007; He et al., 2011)
2008 |  BarterCast (Meulpolder et al., 2008). Type: individual. Peers measure up- and download rates and calculate subjective reputational values using a maxflow algorithm. |  Given upload rate $f_{ji}$ and download rate $f_{ij}$:
$R_{ij}=\frac{arctan(\gamma(f_{ji}-f_{ij}))}{\pi/2}$ |  (Pouwelse et al., 2008)
2009 |  IPGroupRep (Zhang et al., 2009). Type: neighbourhood. Adopts IP-based groups and aggregates spam detection feedback for reputation values. |  Given positive and negative feedback $r_{i}$ and $s_{i}$:
$R_{i}=\frac{r_{i}+1}{r_{i}+s_{i}+2}$ |  (Xie et al., 2007; Thomas, 2010; Esquivel et al., 2010)
2010 |  ARRep (Wang et al., 2010). Type: individual. Leverages direct experiences with recommendations. |  $R_{ij}=\alpha\cdot R_{ij}^{D}+(1-\alpha)\cdot R_{ij}^{R}$ |  (Xiong and Liu, 2004; Gauthier et al., 2004; Huynh et al., 2006; Abdul-Rahman and Hailes, 2000; Keung and Griffiths, 2008)
2011 |  Trust by Association (Kellett et al., 2011). Type: acquaintances. Invite-only network; reputation of the invitee directly affects inviter. |  Given some underlying reputation mechanism $U$:
$R_{i}=(1-\alpha)U_{i}+\alpha\frac{\sum_{j\in N_{i}}U_{j}}{|N_{i}|}$ |  (Rogers and Bhatti, 2007)
2012 |  Souche (Xie et al., 2012). Type: acquaintances. Frictionless vouching and assumes all benevolent users are member of a giant connected component. |  Given a giant connected component (GCC), which growth is limited for each time interval:
$R_{i}=\begin{cases}\text{Trusted},&\text{if }i\in GCC\\\ \text{Not trusted},&\text{otherwise}\end{cases}$ |
2015 |  SocialTrust (Chen et al., 2015). Type: acquaintances. Prefer friends over strangers. Relies on reputation of strangers if no friend available. |  Entity’s reputation is modified based on the rating of the other party and their impact factor $T_{i}$:
$T_{i}=\beta\frac{R_{i}}{R_{max}}+(1-\beta)\frac{D_{i}}{D_{max}}$ |  (Kamvar et al., 2003)
2022 |  MeritRank (Nasrulin et al., 2022). Type: individual. Defines set of strategies to make Sybil prone reputation mechanisms Sybil tolerant. |  Transitivity decay, connectivity decay and epoch decay applied on existing reputation mechanisms. |

##  2\. Background

Shaping trust in the online world, arguably the telos of all reputation
mechanisms, is a hard challenge, which has been studied as early as 2002 (Gil
and Ratnakar, 2002; Douceur, 2002; Mui et al., 2002). As the space of defense
mechanisms gradually evolves, so does the space of attack possibilities. For
instance, people are getting more aware of the risk of the internet and start
to become sceptic towards (spam)mails, causing scammers to invent more
intelligent and sophisticated scams (Binks, 2019). Another example of the need
for online trust is in the world of e-commerce, where criminals are actively
attempting to swindle innocent users on large e-commerce platforms, like eBay
(Bogenschneider, 2021).

Nowadays, this responsibility of creating trust cannot be entrusted to private
corporations. In recent events, Alphabet Inc. (e.g. Google) has been fined
€220 million by French authorities for abusing its dominance in the
advertisement industry. The French government has accused Google of promoting
their own advertisements over their competitors’. Furthermore, in 2019, Google
has been fined €1.28 billion by the European Union on similar charges (Read,
2021). Google’s dominance in the advertisement industry and the abuse of their
position manifests their absolute control over the ranking of advertisements
and online resources, incentivizing one to dispute their role in creating
online trust. This case shows a typical example of the Red Queen hypothesis,
which, in the general case, states that biological species must consistently
adapt to their ever-evolving ecosystem in the eternal fight for survival (Van
Valen, 1973). In our e-commerce setting, this hypothesis corresponds to the
ever-present necessity for companies to adapt to stay ahead of their evolving
competition (Ghose, 2018). Such online wars only help in creating distrust
between different parties, strengthening the need for widely accepted trust
mechanisms. Lastly, the United States House of Representatives has composed a
report assessing the power wielded by the 4 largest bigtech corporations:
Facebook, Google, Amazon and Apple. These companies have become monopolies in
different spaces of the internet, providing them with absolute power. It has
been found that these corporations are abusing this power through “charging
exorbitant fees, imposing oppressive contract terms, and extracting valuable
data from the people and businesses that rely on them” (449, 2020).

Exploiting social phenomena for the purpose of creating trust in online
settings has previously been considered with the proposal of a novel peer-to-
peer file-sharing system, named Tribler (Pouwelse et al., 2008). Tribler is a
peer-to-peer file-sharing system, which introduces social ties to incentivize
users not to misbehave at the expense of their friends, partners or community.
Tribler suggests the usage of public and private keys as an authenticational
method for recognizing previously encountered users in the anonymous peer-to-
peer environment, enabling users to keep track of benevolent and malicious
interactions.

##  3\. Terms and definitions

This section provides the formal definitions of various concepts and data
structures we use in the description of existing social reputation mechanisms.

Entity $-$ The notion of an entity encapsulates any type of instance which may
participate in the network employing the underlying social reputation
mechanisms. For example, an entity may be a real person, but could also be a
computer.

Reputation mechanism $-$ We adopt the definition of reputation mechanism as
formulated by Swamynathan: “A reputation mechanism collects, aggregates, and
disseminates feedback about a user’s behavior, or reputation, based on the
user’s past interactions with others” (Swamynathan et al., 2010). In other
words, a reputation mechanism processes feedback received from all entities
participating in the network to cumulatively calculate a subjective or global
reputation value for each entity.

Trust $-$ In the context of computing systems, we may adopt the definition of
trust as formalized by Saputra: “Trust is a Trustor’s level of confidence in
regard to the ability of a Trustee to provide expected result in an
interaction between Trustor and Trustee” (Saputra, 2020), where a trustor is
the party which receives some service and the trustee is the party entrusted
with performing or providing the trustor with a certain service or resource.
In other words, trust is the certainty at which entity A (trustor) believes
that entity B (trustee) is able to provide them with some service. More
formally, trust is defined as a weighted directional relation $(i,j,v)\in E$
between two entities $i,j\in N$ and $v\in\mathbb{R}$, where $N$ is the set of
all entities, $E$ is the set of all directed relations between two entities
and $v$ is the trustworthiness value assigned by some entity $i$ to some
entity $j$.

Trust graph $-$ Trust relations as defined previously can be aggregated in a
directed graph. We call such graph a trust graph, or alternatively social
graph. This graph is defined by the tuple $(V,E)$, where $V$ is the set of
entities and $E$ is the set of trust relationships, also referred to as edges.
Such a trust graph often facilitates the necessary structural foundation. More
specifically, we say that if some entity $i$ which has had sufficient
(in)direct interaction with some arbitrary entity $j$, such that $j\in N_{i}$
and $\exists(i,j,v)\in E:v\in\mathbb{R}$, where $N_{i}$ is the called a trust
set, consisting of entities with whom entity $i$ has had sufficient
interaction with to assess their trustworthiness, depending on the underlying
reputation mechanism. Furthermore, entities can occur in multiple trust sets,
but no entity can contain itself in its trust set: $\forall i\in N:i\notin
N_{i}$. Additionally, all entities occur at most exactly once in every trust
set, such that $\forall i\in N:\\{\forall j,k\in
N_{i}:ID(j)=ID(k)\Leftrightarrow j=k\\}$, where $ID$ is a deterministic
implementation-specific function capable of identifying individual entities.
Note that the prior implies that $\forall(i,j,v)\in E:i\neq j$. We argue that
every directional relation in the graph is unique, such that
$\forall(i,j,v),(k,l,w)\in E:\\{(i=k\land
j=l)\Leftrightarrow(i,j,v)=(k,l,w)\\}$. Finally, all entities occur exactly
once in a trust graph: $\forall i,j\in N:\\{ID(i)=ID(j)\Leftrightarrow
i=j\\}$. An example of a trust graph representing the trust relations between
nodes A, B and C can be found in Figure 1. In this example, C has a
trust/reputation value of 0.8 in B’s perspective, implying that $(B,C,0.8)\in
E$. The reputation value is calculated and interpreted by the underlying
reputation mechanism. Furthermore, B’s trust set corresponds to
$N_{B}=\\{C\\}$ and A’s trust set to $N_{A}=\\{B,C\\}$.

Figure 1. Example trust graph representing trust relations between entity’s A,
B and C.

Sybil attacks $-$ The Sybil attack (Douceur, 2002) is a well-known attack used
against reputation mechanisms. Many reputation mechanisms are unable to
distinguish original entities from their copies (Levine et al., 2006); a
weakness abused by the Sybil attack. An adversary may employ the Sybil attack
to increase its own reputation through the instant creation of virtual
entities, such that they may enjoy the benefits of high reputations. The
method used to increase one’s reputation using ‘Sybil entities’ depends
heavily on the implementation details of the underlying social reputation
mechanism. In 2011, Seuken et al. have shown that under specific
circumstances, there exists a passive strongly beneficial Sybil attack (Seuken
and Parkes, 2011). In such an attack, a malicious entity can obtain an
infinite gain with minimal effort.

##  4\. Individuals

In the individual scope, no two entities have any initial subjective
reputation value of each other and all reputations are based on the work the
entities perform. However, once an entity has attained the trust of some other
entity, it might propagate this trust value to peers, depending on the
underlying mechanism. A physical social phenomenon resembling such situation
is a networking event. During networking events, no two people have any
initial measures of trust of each other, but any two people may grow to trust
each other through reciprocity. The gradual creation of such trust relations
may be used to form a trust graph. The assessed trustworthiness may then be
shared throughout one’s ‘network’, such that someone can obtain a reputation
value of an entity, which whom they did not have direct interaction.

While direct experience with an entity is the most reliable metric to assess
the trustworthiness of an entity (Sabater and Sierra, 2005), sociological
research has found that reputational values are often spread through gossip
(Feinberg et al., 2014). Recipients of such reputational values have been
shown to use these to selectively interact with cooperative rather than
selfish individuals. An example of a reputation mechanism adopting this social
behaviour in an online setting is ARRep (Wang et al., 2010).

### ARRep

ARRep (adaptive and robust reputation mechanism) (Wang et al., 2010) is a
social reputation mechanism which leverages direct experience with reported
experiences from other entities. While ARRep is proposed for usage in a peer-
to-peer environment, the resemblance with the social phenomenon as depicted
previously is vivid. Furthermore, ARRep applies heuristic for improving the
accuracy of reported experiences, by giving more weight to entities who have
had more experiences.

Given some entity $i$ assessing the trustworthiness of some entity $j$, $j$’s
overall reputation value $R_{ij}$ can be calculated according to:

$R_{ij}=\alpha\cdot R_{ij}^{D}+(1-\alpha)\cdot R_{ij}^{R}$

where $R_{ij}^{D}$ represents the reputation value extracted from $i$’s direct
experience with $j$, $R_{ij}^{R}$ corresponds to the reputation value
extracted from the recommendation of peers, and $\alpha$ represents the
confidence factor of $i$’s direct experience. For some threshold $M>0$,
$\alpha$ is equal to the ratio between the number of experiences and $M$ while
the number of experiences is lower than $M$, otherwise $\alpha=1$. The value
of $R_{ij}^{D}$ corresponds to:

$R_{ij}^{D}=\frac{\sum_{k=1}^{n_{ij}}(\lambda^{n_{ij}-k}\cdot
ex^{k}_{ij})}{\sum_{k=1}^{n_{ij}}\lambda^{n_{ij}-k}}$

where $n_{ij}$ is the total number of interactions between $i$ and $j$,
$\lambda$ is some decay value such that $0<\lambda\leq 1$ and $ex$ is a
function returning either 1 (good) or 0 (bad) depending on the experience of
interactions between $i$ and $j$ from $i$’s perspective. Moreover, the
recommended reputation value $R_{ij}^{R}$ is calculated, such that:

$R_{ij}^{R}=\frac{\sum_{i\neq k}(C_{ik}\cdot
R_{ik}^{D}\cdot\eta^{1/n_{kj}})}{\sum_{i\neq k}C_{ik}}$

where $\eta$ denotes some value $0<\eta\leq 1$ and $C_{ik}$ corresponds to the
recommendation credibility based on the similarity between entity $i$ and the
recommender $k$ (see (Wang et al., 2010) for details).

During evaluation, it was found that ARRep outperforms existing work (Xiong
and Liu, 2004) in a number of attacks for which peer-to-peer networks are
susceptible. More specifically, ARRep has shown to performs better in on-off
attacks, bad mouthing attacks and collusive cheat attacks.
There exist several reputation mechanisms similar to ARRep, focused on the
same principles of combining direct experience with recommendations (Xiong and
Liu, 2004; Gauthier et al., 2004; Huynh et al., 2006; Abdul-Rahman and Hailes,
2000; Keung and Griffiths, 2008). Continuing on the phenomenon in which
reputation may be passed on through gossiping, an example of a reputation
mechanism which directly applies this, is PageRank. PageRank uses the number
of references an entity receives to determine its reputation compared to
others. This behaviour is again very similar to that during networking events.
PageRank has been used for assigning reputation values in social networks
(Hogg and Adamic, 2004) or to measure academic reputation through citation
graphs (Massucci and Docampo, 2019).

### PageRank

In the early ages of the internet, Google was among the first to adopt a
reputation mechanism. Larry Page, Google’s co-founder, introduced PageRank
(Page et al., 1999): an algorithm used to rank search engine results based on
relevance. While PageRank might no longer be Google’s only reputation
mechanism, it is the basis of numerous other reputation mechanism (Zhang et
al., 2017; Bi et al., 2008; Wang et al., 2008; Pujol et al., 2002).

PageRank considers the internet as a network of web pages connected through
their links. If many pages link to another page, it has a higher reputation
and therefore a higher ‘rank’ on the search results page. PageRank’s algorithm
employs the usage of rounds: initially, every page has the same amount of
‘rank’. Every subsequent round, the rank flows uniformly distributed over all
outgoing links to other web pages. An example execution of PageRank is
displayed in Figure 2, in which the edges represent links between web pages.
In round $n$, pages (or entities) have a specific amount of rank. In round
$n+1$, the rank is propagated over the outgoing edges. Web page 3 passes the
0.7 rank over its only outgoing link while receiving 0.5 from web page 1 and
$\frac{1.2}{2}$ from web page 2. Web page 1’s rank is lowered and web page 2’s
rank is stationary. This process continues until the amount of rank for all
pages becomes stationary. Once the network reaches a stationary state,
extracting the final amount of rank per web page is trivial. One may note that
this algorithm shows high similarity to finding the limiting probabilities of
a Markov chain.

Let A be a matrix such that $\forall(i,j,v)\in E:A_{i,j}=\frac{1}{|N_{i}|}$.
Note that the value $v$ is not used by PageRank as it utilizes the notion of
global reputation, i.e. the reputation is equivalent from all perspectives.
Let R the reputation value of web page i, such that:

$R_{i}=c\sum_{v\in B_{i}}\frac{R_{i}}{|N_{i}|}$

where $B_{i}$ is the set of states $\\{j\in N\ |\ i\in N_{j}\\}$ and c is a
factor used for normalization, ensuring the total amount of ‘rank’ remains
constant. When R reaches a stationary state, i.e. it does not change anymore,
it is an eigenvector of matrix A, such that $A=cAR$. However, if the trust
graph takes the shape of a directed cyclic graph, loops with no outgoing edges
may occur, causing the accumulation of rank over time. To tackle this issue,
Page a new formula for reputational values R’ of web page i, such that
$R_{i}^{\prime}=R_{i}+cS_{i}$, where $||R^{\prime}||_{1}=1$ and $S_{i}$ is a
vector of web page i which corresponds to the rank originating from each page.
As we have that $||R^{\prime}||_{1}=1$, c must be reduced when S is an all-
positive vector, implying that c is a decay factor.

The original version of PageRank as described above is prone to Sybil attacks,
as has been shown in many studies (Cheng and Friedman, 2006; Dinh and Ryan,
2008; Danezis and Schiffner, 2006; Chang and Wu, 2012). Such an attack would
introduce many new entities who all link to the attacker, thereby increasing
its reputation. This process is also known as ‘link farming’ (Danezis and
Schiffner, 2006). The original PageRank algorithm does by itself not contain
any defense mechanisms against Sybil attacks.
PageRank makes use of the notion that reputation/rank flows through a network
over directed edges. However, this is not the only use case of directed edges.
Another example of a use case are maxflow algorithms, in which the weights of
the edges can be exploited to find the maximum flow rate between entities.
BarterCast is a reputation mechanism which makes use of such a maxflow
algorithm to help determine an entity’s subjective reputation and
trustworthiness.

### BarterCast

Designed for peer-to-peer settings and deployed in Tribler (Pouwelse et al.,
2008), BarterCast (Meulpolder et al., 2008) integrates up- and download rates
of peers into a directed graph. By using a maxflow algorithm (e.g. Ford-
Fulkerson (Ford and Fulkerson, 1957)), one can find the net up- and download
rates among (in)directly connected peers. These rates are integrated through
the arctan function in which -1 corresponds to a lower bound for the amount of
reputation, 0 represents a neutral position (i.e. newcomers), and 1 is the
upper bound on the reputation one could attain.

More specifically, entities employing the BarterCast protocol aggregate their
own up- and download speeds grouped by the entity with whom they are currently
transferring files. These statistics are shared with known peers periodically,
through messages known as the BarterCast messages. Note that entities do not
propagate messages they receive, implying that any given entity merely
accumulates information of entities at most 2 hops away, which is in turn used
for creating a local view of the network in the form of a directed graph. When
any entity i wants to transfer files to/from entity j, they perform a maxflow
algorithm to determine the net up- and download rate between itself and entity
j, which are represented by $f_{ij}$ and $f_{ji}$, respectively. Using these
values, a reputation value $R_{ij}$ is computed, such that:

$R_{ij}=\frac{arctan(\gamma(f_{ji}-f_{ij}))}{\pi/2}$

where $\gamma$ is a scaling factor. The usage of the arctan function has a
double incentive. Firstly, it bounds the reputation such that
$R_{ij}\in(-1,1)$. Second, it ensures that changes in the net up- and download
rate on a lower scale have more impact compared to a larger scale, e.g. the
difference between 0KB and 100KB affects the reputation more significantly
compared to 800KB and 900KB, which eases the process for newcomers. The
resulting trust graph has strong similarities with real social networks, as
entities can have high reputation in entity $i$’s perspective while having a
low reputation in entity $j$’s point of view, depending on the network
topology.

Along with a metric for reputation calculation, BarterCast is designed with a
built-in resilience against the purposeful spread of false information. As all
entities keep track of both their up- and downloading rate, the outcome of any
correctly implemented maxflow algorithm is (upper) bounded by the statistics
measured by the entity itself. However, reliance on a maxflow algorithm is
accompanied with a risk for Sybil attacks, as maxflow algorithms are prone to
Sybil attacks as shown by (Nasrulin et al., 2022). Through parallel attacks,
adversaries can trivially exploit this vulnerability and obtain infinite
resources.
All prior discussed reputation mechanisms are part of the family of symmetric
reputation mechanisms. In such reputation mechanisms, one’s reputation only
depends on the topology of the trust graph, which makes them generally prone
to Sybil attacks (Levine et al., 2006). However, such reputation mechanisms
can be extended with defense mechanisms to increase their overall Sybil
proofness. An example of a defensive mechanism against Sybil attacks is
MeritRank, which wraps existing social symmetric reputation mechanisms and
adds additional constraints, providing these mechanisms with Sybil attack
tolerance.

Figure 2. Two rounds of the PageRank algorithm.

### MeritRank

MeritRank (Nasrulin et al., 2022) is a novel reputation mechanism which main
goal is to bound the gain of Sybil attacks. That is, MeritRank does not
attempt to solve Sybil attacks, but merely defines a number of strategies
towards tolerating them. Furthermore, MeritRank generically assumes the
existence of an underlying implementation for communication and reputation
calculation using a ‘flow-based’ network, much alike the implementation used
by PageRank.

Trust graphs satisfying MeritRank’s constraints are shown to be Sybil
tolerant. That is, for some value $0<c<\infty$ and Sybil attack $\sigma_{S}$,
the following holds:

$\lim_{|S|\to\infty}\frac{\omega^{+}(\sigma_{S})}{\omega^{-}(\sigma_{S})}<c$

where $S$ is the set of Sybils, $\omega^{+}$ is a function returning the gain
for a Sybil attack and $\omega^{+}$ is a function returning the amount of loss
for a Sybil attack. By defining certain properties for trust graph, MeritRank
is capable of bounding the amount of gain an attacker can get from attacking
the network. Such an attack is also known as a weakly beneficial Sybil attack
(Stannat et al., 2021), which contrasts an attack where an adversary can
obtain infinite gain, also known as a strongly beneficial Sybil attack. The
constraints which MeritRank poses the trust graph are relative
feedback/reputation, connectivity decay, transitivity decay and epoch decay.

The aforementioned constraints are a set of intuitive measures to bound the
gain of an adversary. Relative feedback limits the amount of reputation an
entity can give to some other entity by its own degree. More specifically, the
updated function for assigning reputation is defined as:

$\bar{w}(i,j)=\frac{w(i,j)}{\sum_{k\in N_{i}}w(i,k)}$

where $w$ is the original function for assigning reputation. Note the sum of
reputation/feedback an entity assigns to its neighbours consistently equals 1.
Transitivity decay defines a probability $\alpha$ which is equivalent to stop
a random walk (see the Random Surfer model (Page et al., 1999)) for reputation
determination for any given entity. Furthermore, connectivity decay defines a
constant $0\leq\beta\leq 1$ and ratio $t$, such that if for some entity $i$
(transitively) connected to some entity $j$ through some entity $k$ for at
least the ratio $t$ of all possible paths, $(1-\beta)$ serves as a punishment
factor for decreasing the reputation of the entity $j$ in $i$’s perspective.
The connectivity decay constraint’s main purpose is to identify and punish
separate components. Lastly, the epoch decay defines a constant $\gamma$,
which indicates the reputation decay with each epoch of the graph,
incentivizing entities to keep performing work to receive reputation.

MeritRank has been evaluated on all constraints separately. It has been shown
that “transitivity decay and connectivity decay can provide a desirable level
of Sybil tolerance” (Nasrulin et al., 2022). On the other hand, it was found
that epoch decay, when naively implemented, may prefer new reputation
assignments over existing reputation assignments. As aforementioned, MeritRank
does not provide resistance against Sybil attacks, but accepts their existence
and introduces a number of possible strategies towards bounding the maximum
gain an attack may muster.
Individually-based social reputation mechanisms are often the most prone to
Sybil attacks, as there exists no other external notion on which to base
reputation calculations. While MeritRank proposes a number of strategies
towards tolerating such attacks, it recognizes their existence and its
inability towards preventing them. Arguably the most effective defense against
Sybil attacks is the usage of fixed identity’s and disabling the arbitrary
creation of new virtual entities. An example of such fixed identity is the
European Digital Identity (eud, 2022), which will enable EU residents to claim
a single online identity. An external party verifying or providing an entity’s
identity is said to be the only way of preventing Sybil attacks (Levine et
al., 2006), as identities cannot instantly be created without the external
party’s permission and verification.

##  5\. Acquaintances

In the scope of acquaintances, we consider social reputation mechanisms which
rely on the existence of real relationships between entities. By leveraging
these existing relationships, one may strengthen the defenses of online social
reputation mechanisms. An example of a social phenomenon leveraging existing
relationships is vouching: “to be able from your knowledge or experience to
say that something is true” (cam, [n. d.]). In the context of reputation
mechanism, vouching may generally be used as a method of putting one’s
reputation at stake. More specifically, in the case where some person (the
voucher) has vouched for someone else (the vouchee), while this vouch was
misplaced, the voucher loses their credibility. As a voucher willingly puts
their reputation at stake for the vouchee, it makes one believe that the
voucher has had prior external experience with the vouchee.

In recent years, the government of the United Kingdom has composed a rigorous
guide as how to use vouches in daily-life situations (gov, 2020). It describes
how people can use vouching for verifying one’s identity. For instance, a
parent has the ability to vouch for their child’s identity. They know their
child well and are certain of their child’s identity, inducing no risk of
vouching for them.

An example of a social mechanism employing vouching is Souche, which can be
deployed on online social networks for protecting real users against fake
accounts, often created for malicious purposes, such as spamming.

### Souche

Souche (Xie et al., 2012) is a vouch-based reputation mechanism developed
partially by Microsoft111https://microsoft.com/. Its main goal is to quickly
be able to distinguish between legitimate and illegitimate users in the
context of online social communities, and to slow down any malicious
undetected users. Souche has been evaluated in simulations utilizing large
anonymized email and Twitter222https://twitter.com/ datasets and has been
shown to accurately identify 85% of legitimate users in an early stage.
Furthermore, Souche can relief users of periodic humanity checks, such as
CAPTCHAs, by only performing a CAPTCHA upon registration.

Souche’s main means for creating relationships between entities, i.e. users,
is through implicit vouching. Such process takes place through by considering
regular activities as vouching. As such, Souche defines a vouch through emails
by the conversation between two users, i.e. both users have written each other
at least two emails for a conversation to be considered a vouch. Moreover,
when modelling such approach to large datasets, it was found that a Giant
Connected Component (GCC) starts to take shape. Such a GCC is a large trust
graph which contains 93% of all users for the e-mail dataset, where the
remaining connected components are orders of magnitude smaller than the GCC.
Souche crowdsources the detection of malicious accounts, by assuming that
malicious accounts are not included in the GCC.

Souche defines a quota $q_{i}$ for each entity $i$ to determine whether an
entity is allowed to vouch for some new entity. Every unit of time, this quota
grows with rate $r$. An entity is allowed to vouch for some other entity when
their quota is larger than 1. Naively, the quota can be defined as:

$q_{i}=(1+r)^{t-b_{i}}-c_{i}-1$

where $t$ is the current time, $b_{i}$ is the time at which entity $i$ joined
the network and $c_{i}$ indicates the number of entity $i$ has already vouched
for. However, in order to approach the growth rate with which online social
networks grow, growth rate $r$ should be configured to have a small value,
such as 0.001 where the time interval equals 1 day. This implies that users
are unable to vouch for any other users during their first registered year. To
tackle this issue, Souche divides the GCC trust graph in subtrees, starting at
the leaves, i.e. entities with no outbound vouches. An example of such a
subtree can be found in Figure 3. In this particular example, A has vouched
for both B and C and C has vouched for E and F. Note that if C were to be
exposed as a malicious entity, it is evident that at least A, B, E and F
should be further investigated, as they share a close relation to C. Souche
subtrees have a size of approximately 50 entities and have a single root.
Within subtrees, entities can freely use the cumulative quota. More
specifically, entity $i$ of subtree $T_{i}$ can vouch for some other entity
when $\sum_{k\in T_{i}}q_{k}>1$. In order to account for the usage of shared
quota, the definition of quota is finalized to:

$q_{i}=(1+r)^{t-b_{i}}-c_{i}-d_{i}-1$

where $d_{i}$ represents the quota used by other entities to retain the total
balance of quota within the network. Note that, due to the exponential growth
of quota, older entities are assumed to be more trusted vouchers.

Other than sharing quota, the subtree data structure serves another purpose,
namely that of assisting in the detection of malicious entities. While Souche
itself does not focus on malicious entity detection, given an existing
detection implementation, Souche can assist by marking an entities’s parent,
siblings or descendants as suspicious. Another defense against malicious
entities is the limited quota per time interval, preventing adversaries from
vouching for other adversaries. Smaller trees will result in less available
shared quota for malicious entities to claim. Finally, Sybil attacks may also
suffer from these features.
Another example of a study applying a vouching-based mechanism has been
employed by the CloudSurfing platform (Lauterbach et al., 2009). This approach
implements a more explicit method of vouching, requires more manual user
interaction, and does not protect users from malicious and potentially fake
entities, but is used as a rating for hosts on the CloudSurfing platform.

Figure 3. Example of a Souche subtree.

On the other hand, there exist other social phenomena leveraging existing
relationships which have been translated to social reputation mechanisms. One
such example includes the usage of invitations. In an offline setting,
invitations are often used to invite people to participate in a certain event.
This social behaviour has been studied and integrated as a core component in
social reputation mechanisms, such as Trust by association, which combines the
usage of invitations with a mechanism similar to vouching.

### Trust by association

Trust by association (TbyA) (Kellett et al., 2011) has been designed for
deployment in a peer-to-peer environment. It utilizes invitations to add new
entities to the network and links the reputation values of the inviter and
invitee, similar to vouching. More specifically, inviters may be punished for
the bad behaviour of their invitees, while incentivized by profiting from the
good reputation of their invitees and the rewards for growing the network. Due
to these reputational incentives, it is assumed that users will only invite
people they already have experience with from another channel, i.e. the
acquaintance. TbyA assumes the following properties of the network:

  * •

Invitation-only network $-$ entities can only join the network through
invitation.

  * •

Homogeneous Resource or Service $-$ entities participate in the network for a
common type of resource or service.

  * •

Bounded Existing Reputation Mechanism $-$ there exists an underlying
reputation mechanism, such that the resulting reputation values are bounded
within a fixed interval. Kellett et al. (Kellett et al., 2011) suggests the
usage of EigenTrust (Kamvar et al., 2003).

  * •

Central Point of Calculation $-$ there exists a central machine on which all
calculations take place.

In its simplest form, the reputation value $R$ for entity $i$, $R_{i}$, is
defined by:

$R_{i}=(1-\alpha)U_{i}+\alpha\frac{\sum_{j\in N_{i}}U_{j}}{|N_{i}|}$

where $U_{i}$ is a function returning the reputation of entity $i$ according
to the underlying reputation mechanism, $N_{i}$ refers to the set of invitees
invited by entity $i$, and $\alpha$ is some value $0\leq\alpha<1$ and is
assumed to be 0 when $|N_{i}|=0$. While (Kellett et al., 2011) only uses this
formula as a starting point to introduce enhancements, the general idea
remains unchanged. These enhancements include rewarding network growth by
varying $\alpha$ depending on the amount of entities invited and support for
recursive reputation, i.e. the reputation of the invitee’s of entity $i$’s
invitees affects entity.

In an effort to measure TbyA’s efficacy, a simulation was performed. It was
found that TbyA performs well in the case where there exists an external party
capable of identifying malicious entities and punishing their inviters. TbyA
is said to be able to turn lawless peer-to-peer networks into networks of
benevolent peers, but requires future work on decentralized methods of
identifying malicious entities.
TbyA uses elements we have previously seen in Souche similar to vouching, as
it punishes the inviter for any bad behaviour shown by their invitees.
However, besides social reputation mechanisms in which you need a voucher to
participate, there also exist less strict mechanisms. One such mechanisms is
SocialTrust, in which anyone can participate, but where existing social ties
are useful. SocialTrust uses the notion that friends are more trusted than
strangers (Li et al., 2008).

### SocialTrust

SocialTrust (Chen et al., 2015) attempts to combine entity reputation values
as well as friendships to provide the best QoS in a decentralized network.
SocialTrust’s main goal is to attempt being served by a friend or, if no
friend is available, the server with the highest global reputation, provided
by a trusted authority. First of all, SocialTrust defines two types
friendship, namely ‘friends’ and ‘partners’, both being bidirectional
relationships. An entity can choose their own friends based on their
experiences in the offline physical world and send a ‘friend request’.
However, partners are assigned by the trusted authority and are defined as
entities with whom a certain entity has had many interactions with. In order
to participate in a partnership, both entities must have a reputation larger
than a certain partner threshold.

When some entity $i$ requires a certain service or resource, it first composes
a list of all possible entities which may pose as server. In this process, the
reputation mechanism takes the current load of entities into account, such
that overloaded entities are not included in the list of possible servers.
After composing the list, entity $i$ scans for any friends or partners and, if
present, selects one of these to request the service or resource. If such
friend or partner does not exist, entity $i$ queries the trusted authority for
the reputations of the possible servers and chooses the server with the
highest reputation.

In SocialTrust, each entity is assigned an impact factor, which represents
both their reputation the amount of damage they could inflict and is used to
calculate entity’s new reputation after an interaction, depending on whether
it cooperates. The impact factor $T$ is defined such that:

$T(i)=\beta\frac{R(i)}{R_{max}}+(1-\beta)\frac{D(i)}{D_{max}}$

where $R$ is a function returning an entity’s reputation, $R_{max}$ is the
maximum achievable reputation, $D(i)$ represents the number of friends and
partners, $D_{max}$ is the maximum number of friends and partners and $\beta$
is some value $0\leq\beta\leq 1$. After each interaction, the client will
provide a service rating of the server, which helps the trusted authority to
calculate the new reputations by taking into account the impact factor.

We consider two cases: an interaction in which both the server and client are
cooperative and an interaction in with the server is cooperative, but the
client is non-cooperative. In the first case, the client will, subsequently to
the interaction, send a service rating to the trusted authority, in which it
rates the server with some value $Y$, such that $0<Y\leq 1$. A cooperative
server will accept this rating and the servers reputation increases by
$\alpha(1+T_{c}\cdot Y)$, where $T_{c}$ is the client’s impact factor and
$0\leq\alpha\leq 1$. The client’s reputation will increase with $\alpha$. On
the other hand, we consider the cases where the client is non-cooperative and
provides no feedback or negative feedback, while the server provided honest
work (the trusted authority checks this by verifying the signatures on the
request and response). In this case, the server is assigned $\alpha$
reputation and the client loses $-\alpha(1+T_{c})$ reputation. Similar
reputation assignments are presented in (Chen et al., 2015) for non-
cooperative servers, in which the server loses reputation. Note that the more
reputation and friends/partners an entity has, the more their reputation is
affected in interactions, promoting honest work for all, regardless of
reputation.

In a performance evaluation, SocialTrust has shown stronger capabilities in
excluding non-cooperative entities from the network compared to EigenTrust
(Kamvar et al., 2003), as well as obtaining a more accurate model mapping an
entity’s reputation to its benevolence.
Acquaintance-based social reputation mechanism using concepts like vouching
often offer built-in defenses against attacks. However, bootstrapping such
mechanisms is a challenge, as they often require an initial set of trusted
entities from which all remaining participants join the network. The concept
of implicit vouching as introduced by Souche might open the opportunities for
deploying vouching-based mechanisms, but may inadvertently punish innocent
entities. Reputation mechanisms such as SocialTrust suffer less from the
bootstrap problem, but have weaker defences for filtering malicious entities.

##  6\. Neighbourhoods

The final scope is focused on the notion of neighbourhoods. In a social
context, one’s neighbourhood often determines their opportunities and success
in later stages of life (Graham, 2018). Moreover, social groups often arise
from these neighbourhoods. These groups may determine one’s reputation as it
has been shown that social groups are often assigned a single reputational
value (Masuda, 2012).

Similar concepts have been applied in the design of reputation mechanisms. One
such reputation mechanism is GroupRep, in which entity $j$’s reputation in
entity $i$’s perspective may be determined by their group if no direct
interaction has occurred.

### GroupRep

Based on the assumption that in large peer-to-peer networks, two peers will
not often interact more than once, making it hard to profit from direct
experiences between peers, GroupRep (Tian et al., 2006) adopts the notion of
groups to calculate reputational values. By assuming that users with similar
interests in a peer-to-peer environment have constructed virtual groups,
GroupRep provides a framework for calculating reputational values between
groups, between groups and peers and between peers.

In GroupRep, the notion of a trust graph is applied on two scales. On the
first scale, every node in the trust graph are groups of entities in which the
edges represent reputations from the group perspective. The second scale
considers all nodes individual entities, in which the edges represent
reputation values based on direct experiences between entities. Moreover,
GroupRep defines utility $u$ and costs $c$, which represent the gain and costs
from interactions with other entities or entity groups. In general, reputation
is calculated by $\frac{c_{ij}-u_{ij}}{c_{ij}+u_{ij}}$, where $c_{ij}$
represents the cumulative cost some entity or group $j$ has brought entity or
group $i$ and $u_{ij}$ represents the cumulative utility. However, if
$c_{ij}+u_{ij}=0$, a fall-back policy is applied in which a path (on the
group-based trust graph) is searched between $G(i)$ and $G(j)$, where $G$ is a
function returning an entity’s group. Note that for all groups along this
path, including $G(i)$, the most trusted group is selected for each next step.
The reputation of this path is equivalent to the minimum reputation edge on
the path. However, if no such path exists, a stranger policy is applied, in
which the reputation is calculated using the cumulative utility and cost for
all previous interactions with strangers. Note that GroupRep will always first
attempt to find direct reputation values on the trust graph on entity-level,
however, if no such direct edge exists, the group reputation is used for
determining a reputation value. After an interaction, entity $i$ updates its
local information, creating an edge in the entity trust graph, and sends the
rating to its group $G(i)$, which then may sends the rating to group $G(j)$.

Furthermore, GroupRep introduces a methodology for detecting malicious
entities through clustering entities within groups. By assuming two entities
as similar when they have similar reputations on the entities they both have
had interactions with, clustering can take place. It is assumed that a maximum
cluster of similar entities will take shape, in which all entities are deemed
credible.

GroupRep has been compared against two existing reputation mechanisms on the
performance against malicious collusive attacks. It was shown that GroupRep
achieves a higher ratio of success queries (ratio of peers satisfied with the
result of the interaction) and a higher satisfaction level, where satisfaction
represents the average ratio of cumulative authentic file sizes to cumulative
inauthentic file sizes. However, the scope of this evaluation was somewhat
limited and did not include comparison against any well-known reputation
mechanisms.
While entities are still somewhat free to choose which group to join when
using GroupRep, there also exist more discriminative approaches, which may be
associated with originative discrimination. Such methodologies are commonly
adopted in email spam measures where IP addresses are blacklisted. One such
mechanism is IPGroupRep (name similarity with GroupRep is coincidental), which
aggressively groups IP addresses into blocks based on subnets and assigns
single reputation values to these groups based on their behaviour.

### IPGroupRep

IPGroupRep (Zhang et al., 2009) is an aggressive reputation mechanism for
calculating a reputation for IP blocks based on existing spam classifiers. It
only considers groups of IP addresses, rather than leveraging individual
reputations with a group reputation. In (Zhang et al., 2009), it is suggested
to consider cluster IP into blocks of 256 by naively assuming the first 24
bits of all IP addresses in a block static, similar to a 255.255.255.0 subnet
mask. An IP block’s reputation should be decreased when a spam message
originating from this group is detected, while it should be increased upon
sending legitimate messages. Note that IPGroupRep is in itself not capable or
designed to detect spam, but rather to combine the outputs of several existing
spam detection mechanisms and combine these into a single reputation value.

For each group, a sum $r$ and $s$ are defined, representing the aggregation of
positive and negative spam feedback respectively, provided by the numerous
spam detection mechanisms. IPGroupRep applies a beta distribution, where
$\alpha=r+1$ and $\beta=s+1$ and assumes the expected value E(p) to be the
reputation value, such that:

$E(p)=\frac{r+1}{r+s+2}$

If this value $E(p)$ is larger than some threshold $T_{threshold}$, the group
can be assumed trustworthy.

In evaluation it was found that this reputation mechanism shows very high
precision and accuracy compared to existing reputation mechanisms used for the
protection of mail servers. However, we argue that this method may negatively
affect innocent parties within a group by disregarding the individual
reputations. A possible solution to alleviate this is by decreasing the group
sizes or automatically detect dynamic IP address blocks which may be used for
spam (Xie et al., 2007).
While the usage of groups may be effective against spamming and the danger of
strangers, it is very generative and should be implemented cautiously such
that malicious entities cannot hide in highly reputed groups and enjoy their
benefits.

##  7\. Conclusion

In this paper, we have discussed numerous social phenomena on different scales
and reviewed social reputation mechanisms directly adopting the social
phenomena as core component. First, we focused on the individual scope, in
which every entity is responsible for their own reputation and entities may
refer to each other based on past interactions, increasing each other’s
reputation by performing honest work. Secondly, we reviewed the acquaintances
scope, where mechanisms may benefit from existing social ties to create more
secure environments through vouching and friends. In this space, the existing
trust relations are essential and may heavily influence one’s reputation,
compared to the individual scope. Finally, we reviewed mechanisms in the
neighbourhood scope, in which entities may be part of a group which can
greatly affect their reputation. Over the years, many reputation mechanisms
have been proposed, evaluated and criticised. However, the holy grail of a
social reputation mechanism creating secure online trust is yet to be
invented.

## References

  * (1)
  * cam ([n. d.]) [n. d.].  Vouch. In _Cambride Dictionary_. Cambridge University Press.  https://dictionary.cambridge.org/dictionary/english/vouch
  * 449 (2020) 2020\.  Competition in Digital Markets Report.  https://judiciary.house.gov/online-platforms-and-market-power/competition-in-digital-markets-report.htm
  * gov (2020) 2020\.  How to accept a vouch as evidence of someone’s identity.  https://www.gov.uk/government/publications/how-to-accept-a-vouch-as-evidence-of-someones-identity/how-to-accept-a-vouch-as-evidence-of-someones-identity
  * eud (2022) 2022\.  European Digital Identity.  https://ec.europa.eu/info/strategy/priorities-2019-2024/europe-fit-digital-age/european-digital-identity_en
  * Abdul-Rahman and Hailes (2000) A. Abdul-Rahman and S. Hailes. 2000.  Supporting trust in virtual communities. In _Proceedings of the 33rd Annual Hawaii International Conference on System Sciences_. 9 pp. vol.1–.  https://doi.org/10.1109/HICSS.2000.926814
  * Bi et al. (2008) Jun Bi, Jianping Wu, and Wenmao Zhang. 2008.  A trust and reputation based anti-spim method. In _IEEE INFOCOM 2008-The 27th Conference on Computer Communications_. IEEE, 2485–2493.
  * Binks (2019) Adam Binks. 2019\.  The art of phishing: past, present and future.  _Computer Fraud & Security_ 2019, 4 (2019), 9–11.
  * Bogenschneider (2021) Bret Bogenschneider. 2021\.  eBay Frauds: Specific Illustrations and Analysis.  _Loyola Consumer Law Review, Forthcoming_ (2021).
  * Chang and Wu (2012) Wei Chang and Jie Wu. 2012\.  A survey of sybil attacks in networks.  _Sensor Networks for Sustainable Development_ (2012), 497–533.
  * Chen et al. (2015) Kang Chen, Haiying Shen, Karan Sapra, and Guoxin Liu. 2015\.  A Social Network Based Reputation System for Cooperative P2P File Sharing.  _IEEE Transactions on Parallel and Distributed Systems_ 26, 8 (2015), 2140–2153.  https://doi.org/10.1109/TPDS.2014.2346192
  * Cheng and Friedman (2006) Alice Cheng and Eric Friedman. 2006.  Manipulability of PageRank under sybil strategies.
  * Danezis and Schiffner (2006) George Danezis and Stefan Schiffner. 2006.  On Network formation,(Sybil attacks and Reputation systems). In _DIMACS Workshop on Information Security Economics_. 18–19.
  * Dinh and Ryan (2008) Tien Tuan Anh Dinh and Mark Ryan. 2008.  A sybil-resilient reputation metric for p2p applications. In _2008 International Symposium on Applications and the Internet_. IEEE, 193–196.
  * Douceur (2002) John R Douceur. 2002\.  The sybil attack. In _International workshop on peer-to-peer systems_. Springer, 251–260.
  * Enders et al. (2021) Adam M Enders, Joseph E Uscinski, Michelle I Seelig, Casey A Klofstad, Stefan Wuchty, John R Funchion, Manohar N Murthi, Kamal Premaratne, and Justin Stoler. 2021\.  The relationship between social media use and beliefs in conspiracy theories and misinformation.  _Political behavior_ (2021), 1–24.
  * Esquivel et al. (2010) Holly Esquivel, Aditya Akella, and Tatsuya Mori. 2010\.  On the effectiveness of IP reputation for spam filtering. In _2010 Second International Conference on COMmunication Systems and NETworks (COMSNETS 2010)_. 1–10.  https://doi.org/10.1109/COMSNETS.2010.5431981
  * Feinberg et al. (2014) Matthew Feinberg, Robb Willer, and Michael Schultz. 2014\.  Gossip and ostracism promote cooperation in groups.  _Psychological science_ 25, 3 (2014), 656–664.
  * Ford and Fulkerson (1957) L. R. Ford and D. R. Fulkerson. 1957.  A Simple Algorithm for Finding Maximal Network Flows and an Application to the Hitchcock Problem.  _Canadian Journal of Mathematics_ 9 (1957), 210–218.  https://doi.org/10.4153/CJM-1957-024-0
  * Gauthier et al. (2004) Paul Gauthier, Brian Bershad, and Steven D Gribble. 2004\.  Dealing with cheaters in anonymous peer-to-peer networks.  _Proceedings of technical report of University of Washington_ (2004).
  * Ghose (2018) Shomit Ghose. 2018\.  The red queen and the inevitability of the AMAZOOGLE business model.  https://scet.berkeley.edu/red-queen-inevitability-amazoogle-business-model/
  * Gil and Ratnakar (2002) Yolanda Gil and Varun Ratnakar. 2002.  Trusting information sources one citizen at a time. In _International Semantic Web Conference_. Springer, 162–176.
  * Graham (2018) Bryan S. Graham. 2018\.  Identifying and Estimating Neighborhood Effects.  _Journal of Economic Literature_ 56, 2 (June 2018), 450–500.  https://doi.org/10.1257/jel.20160854
  * He et al. (2011) Di He, Zhiyong Peng, Liang Hong, and Yu Zhang. 2011\.  A social reputation management for web communities. In _International Conference on Web-Age Information Management_. Springer, 167–174.
  * Hogg and Adamic (2004) Tad Hogg and Lada Adamic. 2004.  Enhancing reputation mechanisms via online social networks. In _Proceedings of the 5th ACM Conference on Electronic Commerce_. 236–237.
  * Huynh et al. (2006) Trung Dong Huynh, Nicholas R. Jennings, and Nigel R. Shadbolt. 2006.  Certified Reputation: How an Agent Can Trust a Stranger _(AAMAS ’06)_. Association for Computing Machinery, New York, NY, USA, 1217–1224.  https://doi.org/10.1145/1160633.1160854
  * Ji et al. (2007) Wen Ji, Shoubao Yang, Dong Wei, and Weina Lu. 2007\.  GARM: A Group - Anonymity Reputation Model in Peer-to-Peer System. In _Sixth International Conference on Grid and Cooperative Computing (GCC 2007)_. 481–488.  https://doi.org/10.1109/GCC.2007.70
  * Kamvar et al. (2003) Sepandar D Kamvar, Mario T Schlosser, and Hector Garcia-Molina. 2003\.  The eigentrust algorithm for reputation management in p2p networks. In _Proceedings of the 12th international conference on World Wide Web_. 640–651.
  * Kellett et al. (2011) Matthew Kellett, Thomas Tran, and Ming Li. 2011.  TRUST BY ASSOCIATION: A META-REPUTATION SYSTEM FOR PEER-TO-PEER NETWORKS.  _Computational Intelligence_ 27, 3 (2011), 363–392.
  * Keung and Griffiths (2008) Sarah N Lim Choi Keung and Nathan Griffiths. 2008.  Using recency and relevance to assess trust and reputation. In _Proceedings of AISB 2008 Symposium on Behaviour Regulation in Multi-Agent Systems_ , Vol. 4. 13–18.
  * Lauterbach et al. (2009) Debra Lauterbach, Hung Truong, Tanuj Shah, and Lada Adamic. 2009\.  Surfing a Web of Trust: Reputation and Reciprocity on CouchSurfing.com. In _2009 International Conference on Computational Science and Engineering_ , Vol. 4. 346–353.  https://doi.org/10.1109/CSE.2009.345
  * Levine et al. (2006) Brian Neil Levine, Clay Shields, and N Boris Margolin. 2006\.  A survey of solutions to the sybil attack.  _University of Massachusetts Amherst, Amherst, MA_ 7 (2006), 224.
  * Li et al. (2008) Dan Li, Lorraine Eden, Michael A Hitt, and R Duane Ireland. 2008\.  Friends, acquaintances, or strangers? Partner selection in R&D alliances.  _Academy of management journal_ 51, 2 (2008), 315–334.
  * Massucci and Docampo (2019) Francesco Alessandro Massucci and Domingo Docampo. 2019.  Measuring the academic reputation through citation networks via PageRank.  _Journal of Informetrics_ 13, 1 (2019), 185–201.
  * Masuda (2012) Naoki Masuda. 2012\.  Ingroup favoritism and intergroup cooperation under indirect reciprocity based on group reputation.  _Journal of Theoretical Biology_ 311 (2012), 8–18.
  * Meulpolder et al. (2008) Michel Meulpolder, Johan Pouwelse, Dick Epema, and Henk Sips. 2008\.  Bartercast: Fully distributed sharing-ratio enforcement in bittorrent.  _Delft University of Technology-Parallel and Distributed Systems Report Series_ (2008).
  * Mui et al. (2002) Lik Mui, Mojdeh Mohtashemi, and Ari Halberstadt. 2002\.  A computational model of trust and reputation. In _Proceedings of the 35th annual Hawaii international conference on system sciences_. IEEE, 2431–2439.
  * Nasrulin et al. (2022) Bulat Nasrulin, Georgy Ishmaev, and Johan Pouwelse. 2022\.  MeritRank: Sybil Tolerant Reputation for Merit-based Tokenomics.  _arXiv preprint arXiv:2207.09950_ (2022).
  * Page et al. (1999) Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. 1999.  _The PageRank citation ranking: Bringing order to the web._ Technical Report. Stanford InfoLab.
  * Pouwelse et al. (2008) Johan A Pouwelse, Pawel Garbacki, Jun Wang, Arno Bakker, Jie Yang, Alexandru Iosup, Dick HJ Epema, Marcel Reinders, Maarten R Van Steen, and Henk J Sips. 2008\.  TRIBLER: a social-based peer-to-peer system.  _Concurrency and computation: Practice and experience_ 20, 2 (2008), 127–138.
  * Pujol et al. (2002) Josep M Pujol, Ramon Sangüesa, and Jordi Delgado. 2002\.  Extracting reputation in multi agent systems by means of social network topology. In _Proceedings of the first international joint conference on Autonomous agents and multiagent systems: part 1_. 467–474.
  * Read (2021) Simon Read. 2021\.  Google fined €220m in France over advertising abuse.  _BBC News_ (Jun 2021).
  * Rogers and Bhatti (2007) Michael Rogers and Saleem Bhatti. 2007.  How to disappear completely: A survey of private peer-to-peer networks.  _networks_ 13 (2007), 14.
  * Sabater and Sierra (2001) Jordi Sabater and Carles Sierra. 2001.  REGRET: reputation in gregarious societies. In _Proceedings of the fifth international conference on Autonomous agents_. 194–195.
  * Sabater and Sierra (2005) Jordi Sabater and Carles Sierra. 2005.  Review on computational trust and reputation models.  _Artificial intelligence review_ 24, 1 (2005), 33–60.
  * Saputra (2020) Dany Eka Saputra. 2020\.  Defining trust in computation. In _2020 International Conference on Information Technology Systems and Innovation (ICITSI)_. IEEE, 161–166.
  * Seuken and Parkes (2011) Sven Seuken and David C Parkes. 2011.  On the Sybil-proofness of accounting mechanisms.  _Proceedings of the 2011 Workshop on the Economics of Networks, Systems, and Computation (NetEcon’11)_ (2011).
  * Stannat et al. (2021) Alexander Stannat, Can Umut Ileri, Dion Gijswijt, and Johan Pouwelse. 2021.  Achieving Sybil-Proofness in Distributed Work Systems.. In _AAMAS_. 1263–1271.
  * Sun et al. (2005) Liang Sun, Li Jiao, Yufeng Wang, Shiduan Cheng, and Wendong Wang. 2005.  An adaptive group-based reputation system in peer-to-peer networks. In _International Workshop on Internet and Network Economics_. Springer, 651–659.
  * Swamynathan et al. (2010) Gayatri Swamynathan, Kevin C Almeroth, and Ben Y Zhao. 2010\.  The design of a reliable reputation system.  _Electronic Commerce Research_ 10, 3 (2010), 239–270.
  * Thomas (2010) Ashley Thomas. 2010\.  Rapid: Reputation based approach for improving intrusion detection effectiveness. In _2010 Sixth International Conference on Information Assurance and Security_. IEEE, 118–124.
  * Tian et al. (2006) Huirong Tian, Shihong Zou, Wendong Wang, and Shiduan Cheng. 2006\.  A group based reputation system for P2P networks. In _International Conference on Autonomic and Trusted Computing_. Springer, 342–351.
  * Van Aelst et al. (2021) Peter Van Aelst, Fanni Toth, Laia Castro, Václav Štětka, Claes de Vreese, Toril Aalberg, Ana Sofia Cardenal, Nicoleta Corbu, Frank Esser, David Nicolas Hopmann, et al. 2021\.  Does a crisis change news habits? A comparative study of the effects of COVID-19 on news media use in 17 European countries.  _Digital Journalism_ 9, 9 (2021), 1208–1238.
  * Van Valen (1973) L. Van Valen. 1973\.  A NEW EVOLUTIONARY LAW.  _EVOL. THEORY; U.S.A.; DA. 1973; VOL. 1; NO 1; PP. 1-30; BIBL. DISSEM.; 13 ILL._ (1973).
  * Wang et al. (2008) Jue Wang, Jian Peng, and Daping Zhang. 2008.  Research on Dynamic Reputation Management Model Based on PageRank. In _2008 International Conference on Computer Science and Software Engineering_ , Vol. 3. IEEE, 814–817.
  * Wang et al. (2010) Miao Wang, Fei Tao, Yujun Zhang, and Guojie Li. 2010\.  An Adaptive and Robust Reputation Mechanism for P2P Network. In _2010 IEEE International Conference on Communications_. 1–5.  https://doi.org/10.1109/ICC.2010.5502541
  * Wu et al. (2009) Xu Wu, Jingsha He, and Fei Xu. 2009.  A group-based reputation mechanism for mobile p2p networks. In _International Conference on Grid and Pervasive Computing_. Springer, 410–421.
  * Xie et al. (2007) Yinglian Xie, Fang Yu, Kannan Achan, Eliot Gillum, Moises Goldszmidt, and Ted Wobber. 2007\.  How dynamic are IP addresses?. In _Proceedings of the 2007 conference on Applications, technologies, architectures, and protocols for computer communications_. 301–312.
  * Xie et al. (2012) Yinglian Xie, Fang Yu, Qifa Ke, Martín Abadi, Eliot Gillum, Krish Vitaldevaria, Jason Walter, Junxian Huang, and Zhuoqing Morley Mao. 2012.  Innocent by association: early recognition of legitimate users. In _Proceedings of the 2012 ACM conference on Computer and communications security_. 353–364.
  * Xiong and Liu (2004) Li Xiong and Ling Liu. 2004\.  PeerTrust: supporting reputation-based trust for peer-to-peer electronic communities.  _IEEE Transactions on Knowledge and Data Engineering_ 16, 7 (2004), 843–857.  https://doi.org/10.1109/TKDE.2004.1318566
  * Zhang et al. (2009) Hong Zhang, Haixin Duan, Wu Liu, and Jianping Wu. 2009\.  IPGroupRep: A Novel Reputation Based System for Anti-Spam. In _2009 Symposia and Workshops on Ubiquitous, Autonomic and Trusted Computing_. 513–518.  https://doi.org/10.1109/UIC-ATC.2009.15
  * Zhang et al. (2017) WY Zhang, S Zhang, and SS Guo. 2017.  A PageRank-based reputation model for personalised manufacturing service recommendation.  _Enterprise Information Systems_ 11, 5 (2017), 672–693.