Credit

1]organization=Information Sciences Institute, University of Southern
California, citysep=, country=USA

2]organization=Ontology Engineering Group, Universidad Politécnica de Madrid,
citysep=, country=Spain

3]organization=Dept. of Informatics, Pontificia Universidade Católica Rio de
Janeiro, citysep=, country=Brazil

[1]

Credit

[1]Corresponding author

# A Study of the Quality of Wikidata

Kartik Shenoy<EMAIL_ADDRESS>[  [  [  Filip Ilievski<EMAIL_ADDRESS>Daniel
Garijo<EMAIL_ADDRESS>Daniel Schwabe<EMAIL_ADDRESS>Pedro
Szekely<EMAIL_ADDRESS>
###### Abstract

Wikidata has been increasingly adopted by many communities for a wide variety
of applications, which demand high-quality knowledge to deliver successful
results. In this paper, we develop a framework to detect and analyze low-
quality statements in Wikidata by shedding light on the current practices
exercised by the community. We explore three indicators of data quality in
Wikidata, based on: 1) community consensus on the currently recorded
knowledge, assuming that statements that have been removed and not added back
are implicitly agreed to be of low quality; 2) statements that have been
deprecated; and 3) constraint violations in the data. We combine these
indicators to detect low-quality statements, revealing challenges with
duplicate entities, missing triples, violated type rules, and taxonomic
distinctions. Our findings complement ongoing efforts by the Wikidata
community to improve data quality, aiming to make it easier for users and
editors to find and correct mistakes.

###### keywords:

Wikidata data quality knowledge graphs constraints crowdsourcing

##  1 Introduction

Historically, Wikipedia is the best known knowledge base relying on the
“wisdom of the crowd” (Surowiecki, 2004) to ensure its quality; setting an
example for other popular websites such as Quora111https://quora.com/ and
Stack Exchange.222https://stackexchange.com/ Wikidata (Vrandečić and Krötzsch,
2014) has been created in a similar manner - editing it is fairly
straightforward. Consequently, Wikidata today is a joint creation of tens of
thousands of human and bot contributors (Piscopo and Simperl, 2018). The
result is a rich set of factual statements that describe claims about entities
and events in the real world. New information is entered everyday, resulting
in very high growth rates and immediate description of popular world
events.333In this work, we use the terms statement, claim, and fact
interchangably.

Wikidata aims to allow “plurality of facts” (Möller et al., ), and hence it is
important that these facts are described with high-quality statements. We have
little understanding of the quality of the knowledge contained in Wikidata.
Relatively simple validators can spot syntactic errors, allowing for automatic
detection (‘flagging’ or editing) of syntactically anomalous statements (Beek
et al., 2014). Yet, capturing and correcting semantic information is more
challenging. While existing work has proposed an extensive set of quality
notions (Piscopo and Simperl, 2019), and started to apply statement validation
to Wikidata (Thornton et al., 2019; Piscopo and Simperl, 2018), to our
knowledge, no past work has comprehensively applied indicators to measure
quality of statements in Wikidata as a whole, and provided a vision for
improving its quality in the future.

In this paper, we develop a framework to detect and analyze low-quality
statements in Wikidata by shedding light on the current practices exercised by
the community. In addition, we propose to enhance the quality of Wikidata by
automatically flagging potential problematic statements for editors. Our work
makes the following contributions:

  1. 1.

We define three indicators that measure well-understood notions of quality of
Wikidata statements, based on: 1) the statement revision history of Wikidata;
2) deprecation of statements; and 3) violations of property constraints
defined by the community.

  2. 2.

We develop an efficient framework that flags potential errors integrating
these three indicators of quality. Namely, the community-based indicators find
low-quality statements which have been deleted or deprecated throughout the
history of Wikidata (since its inception in 2014), while the constraint-based
indicator reveals outliers with high constraint violation ratios.

  3. 3.

We apply our framework to analyze the quality of the entire Wikidata.444There
are 1,149,471,184 statements in the Wikidata dump of December 2020. We report
findings on key aspects of quality that affect users and editors, such as low-
quality type statements, taxonomical modeling errors, duplicated nodes, and
missing statements.

  4. 4.

We propose recommended actions to interactively support high-quality
contributions in the future, as well as to retroactively fix existing issues.
By doing so, we complement ongoing efforts by the Wikidata community to
improve data quality based on games and suggestions, aiming to make it easier
to prevent, find, and correct mistakes.

Our quality indicators evaluate the degree of community consensus on what is
acceptable, thus connecting to existing metrics of Wikidata quality, like
accuracy, consistency, and veracity (Piscopo and Simperl, 2019). By analyzing
statements which have been removed, we reflect on the accuracy of the data. By
formulating and analyzing semantic rules (constraints) that statements must
satisfy, we provide insights into the well-formedness and consistency of the
data. The analysis of the deprecated statements addresses the veracity of
claims, by indicating that there was once consensus about their veracity, but
this is no longer the case.

We make our code555https://github.com/usc-isi-i2/wd-quality (Shenoy et al.,
2021b) and materials666https://w3id.org/wd_quality available to facilitate
further work on analyzing quality of Wikidata statements. The rest of the
paper is structured as follows. Section 2 introduces the three indicators,
their formalization, and combination into a joint framework. All of our
findings with their supporting analyses are described in Section 3.
Recommended actions can be found in Section 4. We relate to prior work on
Wikidata quality in Section 5. The paper concludes in Section 6.

##  2 Framework

We seek to measure semantic quality aspects of Wikidata. We devise a framework
for detecting low-quality statements in Wikidata, which combines three
indicators of quality, based on: 1) community updates; 2) deprecated
statements; and 3) property constraints. In this section, we describe each of
the quality indicators and we provide details on their formalization into an
integrated framework that can analyze the quality of Wikidata. We formalize
low quality with $q=0$.

Throughout this section, we use $S$ to refer to a set of statements. A
_statement_ $(s,p,o,Q)\in S$ refers to the union of an edge subject $s$,
predicate $p$, object $o$, and qualifier set $Q$. Qualifier sets contain
property-value pairs $(q_{p_{i}},q_{v_{i}})\in Q$ that further describe the
tuple $(s,p,o)$, (e.g., with the date or the source of assertion). Such
statements are common building blocks of modern hyperrelational Knowledge
Graphs (KGs), like Wikidata or YAGO (Tanon et al., 2020).

###  2.1 Quality Indicators

Community-based indicator We define a community-based indicator of KG quality
by considering that the KG statements that have been permanently deleted by
the community (i.e., statements deleted at a time point $t_{i}$ and not
restored in time points $t_{j},j>i$) are of low quality. Following the idea of
“wisdom of the crowd” (Surowiecki, 2004), we assume that community-based KGs,
like Wikidata, are self-correcting over time, i.e., its contributors detect
low-quality statements, and either delete or replace them.

However, the set of removed tuples by itself is neither necessary nor
sufficient to indicate incorrect statements. A statement might be simply
updated with a semantically equivalent one. Object values may be reassigned
from one property or class to another, which might be considered more
appropriate to express the relationship between the subject and the object.
Literals may be updated with a new value that may or may not be semantically
different than the original one. The latter case often corresponds to the
adoption of new naming conventions, e.g., replacing the name “Pamela C
Rasmussen” with “Pamela C. Rasmussen”. To address these issues, we consider
the low-quality ($q=0$) statements of a dump $d$ at a time $t_{i}$ to be a
union of: 1) the removed statements which were not updated ($R(d_{t_{i}})$),
and 2) the removed statements which were updated with a significantly
different value ($U(d_{t_{i}})$). Formally,
$S_{c}(q=0,d_{t_{i}})=R(d_{t_{i}})\cup U(d_{t_{i}})$.

Deprecation-based indicator Wikidata has a ‘soft’ alternative to deletions:
deprecating statements to indicate consensus about the end of their validity.
A statement is marked as _deprecated_ in two cases: 1) if it has been
superseded by another statement, or 2) if it is now known to be wrong, but was
once thought correct.777https://www.wikidata.org/wiki/Help:Deprecation For
example, the community agreed that Pluto ceased to be a planet since 13th
September, 2006 and hence the claim stating that fact has been deprecated.

Deprecated statements ($D$) are valuable for studying the evolution of
Wikidata and the agreement about its statements. However, they are undesired
when using Wikidata in applications that require up-to-date information, like
entity linking and question answering. Thus, we consider all deprecated
statements of a dump $d$ at a time $t_{i}$ to be indicators of low quality,
formally: $S_{d}(q=0,d_{t_{i}})=D(d_{t_{i}})$.

Constraints-based indicator The Wikidata community has defined property
constraints, i.e., rules that specify how properties should be
used.888https://www.wikidata.org/wiki/Help:Property_constraints_portal Each
property in Wikidata specifies the constraint types that apply to it.
Statements expressed with that property can then either conform to the
constraint or violate it. We denote the set of all violations in a Wikidata
dump $d$ at a time $t_{i}$ with $V(d_{t_{i}})$. Constraints are split in three
groups: mandatory, suggested, and normal (i.e., constraints which are neither
mandatory, nor suggested). Each constraint type is further specified per
property, by stating additional elements: property-dependent classes,
exceptions, and property paths.

Figure 1: Example constraints for the property occupation (P106): type (top-
left), value type (top-right), and item requires statement (bottom). The type
constraint specifies that subjects that have an occupation have to be
instances of one of the eight allowed classes, unless the subject is
prescriber. The value type constraint dictates that objects of occupation
statements have to be either instances or subclasses of one of the six
possible classes shown. The item requires statement constraint specifies that
items which have an occupation value must also have an instance-of statement.
All depicted constraints have a normal status.

At present, Wikidata defines 30 types of property constraints. Constraints
vary in nature, and range from format validation (e.g., correct dates or
naming conventions) to ensuring a consistent usage of a property (e.g., making
sure that symmetric properties are used in both directions). We provide
examples for three key constraint types in Figure 1: type constraint, value
type constraint, and item-requires-statement constraint. The Wikidata type and
value type constraints indicate that the domain of a property (or range,
respectively) has to conform to one of the listed classes, but specify them
further with exceptions and property paths. The item-requires-statement
constraint dictates that a Wikidata item with one property should also specify
another one. Constraints may also specify exceptions. In Figure 1, the type
constraint indicates that subjects that have an occupation have to be
instances of one of the eight allowed classes, unless the subject is
prescriber (“person legally empowered to write medical
prescriptions”),999https://www.wikidata.org/wiki/Q99393050 whereas the value
type constraint dictates that objects of occupation statements have to be
either instances or subclasses of one of the six possible classes shown. The
item requires statement constraint specifies that items which have an
occupation value must also have an instance-of statement. All constraints
presented in this figure have a normal status.

The constraint-based indicator considers violations of property constraints in
their corresponding statements to be low-quality statements.We denote the set
of statements that violate a constraint with $V$. The set of low-quality
($q=0$) statements according to this indicator is:
$S_{v}(q=0,d_{t_{i}})=V(d_{t_{i}})$.

###  2.2 Experimental Setup

While the three indicators of quality have different foci, each of them
identifies a set of low-quality statements, denoted by $S_{c}$, $S_{d}$, and
$S_{v}$ in the previous section. In the rest of the paper, we analyze the low-
quality statements identified by each indicator. We inspect deprecated and
permanently deleted statements in Wikidata, we assess what constraints are
violated, and we compare the violations with the deletions. In our
experiments, we employ the Knowledge Graph ToolKit (KGTK) (Ilievski et al.,
2020), which supports flexible and scalable imports of Wikidata, and supports
efficient manipulation of large hyperrelational KGs, which is essential for
the analysis carried out by our quality framework.

Community-based indicator: We collected a dataset of Wikidata statements that
have been permanently removed (i.e., removed and not added again) since the
first available dump of Wikidata in October, 2014. The dumps of Wikidata are
released weekly. We generated this dataset by downloading all available weekly
JSON Wikidata dumps from the Internet
Archive,101010https://archive.org/search.php?query=wikidata resulting in 311
dumps;111111Approximately two years of dumps were missing from Internet
Archive, but we were able to retrieve them with the help of contributors from
the Wikidata community. converting them to the KGTK format; and extracting
statements that had been removed between each pair of successive dumps
$(d_{t_{i}},d_{t_{j}})$, where $t_{i}<t_{j}$. We also checked whether
statements that have been removed before $t_{i}$ were present in the more
recent of the two dumps, $d_{t_{j}}$. Formally:

$A(d_{t_{i}},d_{t_{j}})=d_{t_{j}}\setminus d_{t_{i}}$, with $t_{i}<t_{j}$

$R(d_{t_{i}},d_{t_{j}})=d_{t_{i}}\setminus d_{t_{j}}$, with $t_{i}<t_{j}$

$Tr(d_{t_{j}})=(Tr(d_{t_{i}})\setminus A(d_{t_{i}},d_{t_{j}}))\cup
R(d_{t_{i}},d_{t_{j}})$, with $t_{i}<t_{j}$

Here, $A$ and $R$ represent the added and deleted statements between
$d_{t_{i}}$ and $d_{t_{j}}$, respectively. The operator $\setminus$ represents
a difference between two sets, $\cup$ is the union, and the total removed
statements for the 0-th dump is $Tr(d_{t_{0}})=\emptyset$

After obtaining the full set of removed statements, we analyzed how many of
the nodes had been redirected to new nodes (i.e., duplicate removal), and
computed the distribution of classes and properties being removed. For
literals, we investigated whether a value had been entirely removed or updated
by computing the similarity between the removed value and the new one. We
analyzed the similarity for each literal type separately. For strings, we
measured Levenshtein distance between the removed and the updated text. For
dates, we measured the time distance between the removed and the updated date.
For quantities, we computed the difference in magnitude between the removed
and the new quantity. We consider deleted statements with no update and
deleted statements with a notable update to be of low quality (cf. Section
2.1).

Deprecation-based indicator: We consider all deprecated statements to be of
low quality. Wikidata indicates deprecation through the rank qualifier of a
statement. We retrieved all statements with a deprecated rank value in the
early Jan, 2021 version of Wikidata (the last dump we collected), and we
explored their distribution in terms of entities and properties.

    kgtk query
    -i statements instance_of subclass_of_star \
    --match statements: (subject)-[id {label:property}]->(object), \
            instance_of: (subject)-[]->(class), \
            subclass_of_star: (class)-[]->(parent)’ \
    --where ’parent in expected_parents or subject in exceptions’ \
    --return ’distinct id, subject, property, object’ \

Figure 2: Example of a query template for the type constraint. The set of
allowed parent classes for the subject are defined in expected_parents,
whereas exceptions is the set of subjects for which this constraint is not
required. If the subject of a statement is an instance of a class in
expected_parents, or any of its subclasses, then the constraint is satisfied
for that statement. The constraint is also satisfied if the subject belongs to
the set of exceptions defined by the property constraint. Notably, for some
properties, the instance of relation is replaced with a subclass of relation.

Constraint-based indicator: We consider statements that violate constraints to
be of low quality, $q=0$. We prioritized constraints that are common in
Semantic Web research and cover a sufficient number of properties (e.g., type
and value type).

Wikidata has pages with constraint violation
reports,121212https://www.wikidata.org/wiki/Wikidata:Database_reports/Constraint_violations
which are calculated with an ad-hoc extension of
Wikibase.131313https://gerrit.wikimedia.org/r/plugins/gitiles/mediawiki/extensions/WikibaseQualityConstraints
However, it is unclear whether these reports are updated regularly. Given the
size of Wikidata, validating its constraints with the Shape Constraint
Language (SHACL) or the Shape Expressions Language (ShEx) is computationally
prohibitive (Boneva et al., 2019). Moreover, it is unclear whether these
languages can encode exceptions and allowed values in property constraints,
and, to the best of our knowledge, there is no available implementation of
SHACL/ShEx constraint validators for Wikidata. For this reason, we encoded
each constraint type as a KGTK query template. Each template is instantiated
once per property, allowing their efficient validation in parallel. Constraint
violations for a property are computed in a two-step manner: we first obtain
the set of statements that satisfy the constraint for a property, and then we
subtract this set from the overall number of statements for that property. We
omit constraints defined on external identifier properties, as our aim is to
capture semantic and modeling errors in Wikidata.

An example query template is shown in Figure 2. The query inspects whether the
subjects for a property are instances of a class that is allowed by the
constraint, or any of its subclasses. If this is the case, or the subject is
listed as an exception to the constraint, then the constraint is satisfied for
this statement. Notably, for some properties, the instance of relation is
replaced with a subclass of relation. A full example query for one property
can be seen in Annex A.

Table 1: Statistics of the constraints: type (Q21503250), value type (Q21510865), item requires statement (Q21503247), inverse (Q21510855), and symmetric (Q21510862). We show the number of properties with (M)andatory, (N)ormal and (S)uggested constraints, and the corresponding number of statements. For the item requires statement constraint type $all\leq M+N+S$, because properties have multiple constraints with a potentially different status. | #properties | #statements | validation time (in sec.)
---|---|---|---
constraint type | all | M | N | S | all | min | max | mean | median
type | 1,456 | 165 | 1,280 | 11 | 513,424,170 | 4.95 | 5231.15 | 366.16 | 174.78
value type | 897 | 106 | 786 | 5 | 182,087,480 | 11.41 | 5323.18 | 352.08 | 144.15
item requires statement | 527 | 78 | 418 | 97 | 302,642,146 | 1.89 | 2199.57 | 133.51 | 58.6
inverse | 110 | 6 | 100 | 4 | 9,440,925 | 8.68 | 646.22 | 100.69 | 54.79
symmetric | 38 | 5 | 30 | 3 | 7,145,197 | 9.72 | 527.33 | 118.44 | 68.67

Combination of indicators: Each quality indicator produces a set of
statements. We compute the overlap between the deleted statements and the
constraint violations as follows. We added all deleted statements to the
Wikidata version where we computed the violations, and calculated the number
of violations without and with the total removed statements: $V$ and
$V_{del}$, respectively. The difference between these two yields the number of
violations that were fixed by the removal of the statements ($V_{fixed}$).
Formally:

$V=V(d_{t_{i}})$

$V_{del}=V(d_{t_{i}}\cup Tr(d_{t_{i}}))$

$V_{fixed}=V_{del}\setminus V$

##  3 Findings

Our framework indicators result in: 1) a dataset of 76.5M removed statements,
describing 26.2M distinct subjects (Garijo and Szekely, 2021); 2) a dataset of
10M deprecated statements (Shenoy et al., 2021c); and 3) a set of correct
statements and constraint violations (Shenoy et al., 2021a), according to the
constraint types specified in Table 1. This table shows that most of the
property constraints have a normal status, and that the median time to
validate a property constraint over Wikidata ranges between 55 and 175 seconds
for the five constraints. This demonstrates the feasibility of our approach to
validate Wikidata constraints at scale.

In this section, we highlight the main findings of our analysis by shedding
light into complex issues related to KG quality, such as node redundancy,
naming conventions, taxonomic distinctions, completeness, accuracy of
constraints, and type consistency. We also explore whether constraint
violations are getting corrected over time, thereby improving the overall
quality of Wikidata. Specifically, we study the following eight research
questions:

  1. 1.

Are entities being deduplicated?

  2. 2.

Can the community distinguish classes from instances?

  3. 3.

Are naming conventions needed?

  4. 4.

Are property types and value types respected?

  5. 5.

Can we detect missing triples?

  6. 6.

Are constraints correct and complete?

  7. 7.

What statements get deprecated?

  8. 8.

Are constraint violations getting fixed?

For each of these questions: 1) we motivate its relevance and impact on
Wikidata; 2) we present our findings about its current state; and 3) we
provide an in-depth analysis and representative examples. Based on these
findings, we provide recommendations about improving the state-of-the-art
quality of Wikidata in Section 4.

###  3.1 Are Entities being Deduplicated?

Entity linking and deduplication are complex open research challenges in many
KGs. Redirects are a common mechanism to deduplicate nodes, and are applied
when a user recognizes that two nodes describe the same subject, e.g.,
Category:1911 in Morocco redirects from Q18511155 to
Q9404406.141414https://www.wikidata.org/wiki/Help:Redirects Our analysis
reveals over 2 million redirected nodes, which affect over 20 million
statements (26% of all removed statements). The relatively high number of
redirects reflects Wikidata’s dynamic nature and the community pursuit for a
high-quality, well-integrated graph. It is not known how many duplicate
entities currently remain in Wikidata.

21.3 million statements (27.8% of the removed statements) have either a
redirected subject or a redirected object. We inspected the property
containing the largest number of redirected items, instance of (P31), to
understand what type of nodes have been redirected. Table 2 (top) shows the
five classes with the highest number of redirected instances, which include
well-populated classes in Wikidata like human, scholarly article, and gene. In
addition, a portion of the instance of (P31) redirects are due to classes that
themselves have been redirected. Table 2 (bottom) shows the five redirected
classes with a highest number of member instances, which include encyclopedic
article, village of Poland, and rotating variable star.

Table 2: Distribution of classes in redirected P31 statements. We show 5
classes with the highest number of redirected instances, and 5 classes that
have been redirected themselves. The counts and the percentages represent
numbers of affected statements. The percentages are relative to total
redirected statements, not total statements. Classes of redirected instances
---
Q4167836 | Wikimedia category | 526,207 (21.38%)
Q5 | human | 222,809 (9.05%)
Q4167410 | Wikimedia disambiguation page | 108,583 (4.41%)
Q13442814 | scholarly article | 101,156 (4.11%)
Q7187 | gene | 88,231 (3.59%)
Redirected classes
Q17329259 | encyclopedic article | 301,359 (12.25%)
Q4423781 | dictionary entry | 53,671 (2.18%)
Q17143521 | village of Poland | 51,581 (2.09%)
Q15917122 | rotating variable star | 50,642 (2.06%)
Q20900710 | painting | 23,482 (0.99%)
Table 3: Community updates of instance-of (P31) and subclass-of (P279). before | after | count | example
---|---|---|---
P31 | P31 | 2.85M | (Hardenstein Castle,P31,geographical feature)
|  |  |  $\rightarrow$ (Hardenstein Castle,P31,ruins)
| P279 | 44k | (laboratory centrifuge,P31,laboratory equipment)
|  |  |  $\rightarrow$ (laboratory centrifuge,P279,laboratory equipment)
| both | 106k | (mystic,P31,person)
|  |  |  $\rightarrow$ (mystic,P31,non-professional work activity)
|  |  |  $\rightarrow$(mystic,P279,religious)
| none | 703k | (Clubland Smashed,P31,album)$\rightarrow$none
P279 | P31 | 444k | (Chemical Markup Language,P279,markup language)
|  |  |  $\rightarrow$ (Chemical Markup Language,P31,markup language)
| P279 | 33k | (girder bridge,P279,bridge by structural type)
|  |  |  $\rightarrow$ (girder bridge,P279,bridge)
| both | 421k | (barn,P279,building)
|  |  |  $\rightarrow$(barn,P31,type of farm house)
|  |  |  $\rightarrow$(barn,P279,agricultural structure)
|  |  |  $\rightarrow$(barn,P279,appendage)
| none | 36.5k | (Categoria:Plantilles d’informació de videojocs,P279,
|  |  | Category:Wikimedia templates) $\rightarrow$none

###  3.2 Can the Community Distinguish Classes from Instances?

When adding new instances to Wikidata, contributors must specify descriptive
values for the taxonomy relations of instance of (P31) and subclass of (P279).
Wikidata’s fairly wide ontology (containing millions of classes) and the prior
evidence on the difficulty of distinguishing between taxonomic relations in
Wikidata (Piscopo and Simperl, 2018), raise the question: can the community
distinguish classes from instances? Our analysis of removed statements with
object properties reveals nearly half a million cases where one of the
taxonomic relations has been changed to the other, which point to the fact
that the community struggles to decide whether to use instance-of (P31) or
subclass-of (P279) to model inheritance in
Wikidata.151515https://www.wikidata.org/wiki/Wikidata:WikiProject_Ontology/Problems

Drilling down, we see that in 44 thousand cases, the instance of statement was
replaced with a subclass of statement. In the case of former P279 edges, the
number of taxonomic switches is notably larger: nearly half (444k out of 935k)
P279 edges were replaced by a P31 edge only. Illustrative examples in Table 3
indicate that these switches often happen in cases where it is not trivial to
distinguish between the two taxonomic relations. For example, the community
struggles to specify the membership of laboratory centrifuge as laboratory
equipment - a former instance of relation has been replaced with a subclass of
one. Conversely, the Chemical Markup Language used to be specified as a
subclass of a markup language, but this has been corrected into an instance of
relation. In both cases, the updated relation seems more intuitive, which, in
line with the “wisdom of the crowd” assumption, would indicate that switches
between the two relations largely reflect fixes of prior modeling errors.

Figure 3: Distribution of the Levenshtein distance between old and new string
values. The x-axis shows the Levenshtein distance, while the y-axis shows
number of statements in each bucket, in terms of millions.

###  3.3 Are Naming Conventions Needed?

To our knowledge, Wikidata does not prescribe how to encode strings, though
there are guidelines for dates.161616https://www.wikidata.org/wiki/Help:Dates
We performed an analysis to investigate the proportion of updates for both
strings and dates, in order to study current practices, and possible
oscillations between different semantically equivalent values. Our analysis
reveals that the community has already performed millions of updates between
semantically (nearly) equivalent forms of literals.

In particular, we observe that in the majority of cases (61.5% of all removed
dates), the date was replaced with a semantically equivalent date with a
different surface form. An example is the year 1964, modified from
“000000001964-00-00T00:00:00Z/9” to “1964-00-00T00:00:00Z/9”. When it comes to
removed string statements, we observe that 46% of them (14 million) have been
replaced with new values. The distribution of the Levenshtein distances
between the old and the new string values is shown in Figure 3. We observe
that strings with low Levenshtein distances are typically stylistic updates,
e.g., from “Pamela C Rasmussen” to “Pamela C. Rasmussen”. Among the strings
with a medium Levenshtein distance (of 10), we see updates which are meant as
specifications and can also be interpreted as mere stylistic adaptations, such
as the update of “Hiroshima EAST BLD” to “Hiroshima East Building”. The
strings with a large distance (of 20) are generally different from the
original strings, such as the update of “Meredith Boyle Metzger” to “Susan
Michaelis”.

Table 4: Correct (constraint-satisfying) and incorrect (constraint-violating) statements for the five constraint types analyzed in this paper: type (Q21503250), value type (Q21510865), item requires statement (Q21503247), inverse (Q21510855), and symmetric (Q21510862). The violation ratio (VR) is the percentage of incorrect statements in the total set of statements in a given category. We separate the statistics among (M)andatory, (N)ormal and (S)uggested constraints. | mandatory | normal | suggested
---|---|---|---
constraint type | correct | incorrect | VR% | correct | incorrect | VR% | correct | incorrect | VR%
type | 44.99M | 37.67k | 0.08 | 464.71M | 3.58M | 0.76 | 85.03k | 21.65k | 20.29
value type | 11.44M | 5.38k | 0.03 | 169.47M | 1.11M | 0.65 | 46.15k | 512 | 1.09
I.R.S. | 3.98M | 767 | 0.02 | 272.71M | 2.25M | 0.82 | 25.73M | 2.24M | 8.01
inverse | 6.56k | 133 | 1.99 | 7.13M | 0.21M | 2.79 | 2M | 95.35k | 4.55
symmetric | 7.43k | 42 | 0.56 | 6.23M | 78.88k | 1.25 | 0.77M | 54.22k | 6.55
Figure 4: Distribution of Violation Ratios (VRs) for each of the five
constraints. Each dot corresponds to a single property. Properties are shown
in a descending order according to their VRs. The number of points varies
according to constraint usage.

###  3.4 Are Property Types and Value Types Respected?

Type and value type constraints are similar to the domain and range
constraints in Semantic Web languages like OWL, and are covered in resources
like YAGO (Tanon et al., 2020) and VerbNet (Schuler, 2005). Many properties in
Wikidata have associated type and value type constraints, as shown in Table 1.
Have these constraints been respected by the data? We observe that only a
small portion of the mandatory constraints, and a much larger portion of the
suggested constraints, violate the set constraints. While the violations are
largely concentrated around a small set of properties and could in theory be
fixed, it is unclear whether this is desired, as the suggested status implies
that they might not need to be strictly enforced.

As shown by the violation ratios in Table 4 (rows 1 and 2), only a small
portion of the mandatory type and value type constraints are violated (0.08%
and 0.03%, respectively). The proportion of violations is larger for normal
constraints, which represent the majority (0.76% and 0.65%, respectively). The
violation ratio is the highest for the suggested constraints, where as many as
20% of the statements were found to violate type constraints. This might be
expected, as the status suggested implies less strict semantics than mandatory
constraints. This analysis entails that fixing the current type and value type
violations would require nearly 44 thousand edits for the mandatory
constraints, and 4.7 million edits for the normal and suggested constraints.
Figure 4 shows a Zipfian distribution of the violation ratios for the
properties that have type and value type constraint, i.e., most violations are
concentrated around a few properties.

Table 5: Top-3 constraint violations for each constraint type. The violation ratio (VR%) is the percentage of incorrect statements in the total set of statements for a given property. constraint | property | label | VR% | #statements
---|---|---|---|---
type | P8138 | located in the statistical territorial entity | 100 | 461
| P5051 | towards | 100 | 64
| P2303 | exception to constraint | 100 | 39
value type | P5008 | on focus list of Wikimedia project | 100 | 331,026
| P6104 | maintained by WikiProject | 100 | 9,764
| P7374 | educational stage | 100 | 32
i.r.s. | P1111 | votes received | 100 | 46,327
| P2302 | property constraint | 100 | 42,211
| P3063 | gestation period | 100 | 549
inverse | P1605 | has natural reservoir | 94.03 | 201
| P3448 | stepparent | 87.97 | 4,849
| P926 | postsynaptic connection | 85.71 | 7
symmetric | P5188 | Sandbox-Lexeme | 100 | 2
| P1706 | together with | 92.85 | 56
| P521 | scheduled service destination | 75.67 | 1,718

###  3.5 Can we Detect Missing Triples?

It is well known that broad-coverage KGs are inherently incomplete (Dong et
al., 2014). This incompleteness can be partially addressed through the
property constraints: item-requires-statement (IRS), inverse, and symmetric.
These constraints point to a missing triple for the same entity, a missing
triple with an inverse property, and with a symmetric property, respectively.
For example, IRS dictates that entities that have an occupation property must
also have a statement with the instance of property. We investigate to which
extent these constraints have been followed by the statements in Wikidata. As
shown in Table 4, the mandatory constraints for these constraint types reveal
nearly a thousand violations, which may indicate missing triples. The
situation worsens for normal and suggested constraints, whose enforcement
would lead to millions of potentially missing triples. While fixing symmetric
and inverse constraints is programmatically trivial, it is unclear whether
this is always desired, as the constraint violations may be caused by an
incorrect original statement rather than a missing one. For example, if a
spouse link exists from entity $E_{1}$ to $E_{2}$, but not from $E_{2}$ to
$E_{1}$, it is impossible to infer automatically whether $E_{1}$ and $E_{2}$
are spouses (in which case a link from $E_{2}$ to $E_{1}$ is missing) or not
(in which case the link from $E_{1}$ to $E_{2}$ should be removed).

Table 4 (rows 3-5) illustrates how mandatory IRS and inverse constraints are
largely followed (with only 0.02% and 1.9% violations, respectively). As
expected, the violation ratios are larger for normal, and largest for
suggested constraints, peaking at 8% for the IRS suggested constraints. Table
5 shows examples for properties with highest violation ratios. For instance,
the property votes received (P1111) requires other properties like office
contested (P541) to be present, which is violated in all 46k cases where it
appears. The inverse property for the properties has natural reservoir (P1605)
and stepparent (P3448) is missing in nearly all cases, resulting in five
thousand violations. The most commonly violated symmetric properties include
Sandbox-Lexeme (P5188), together with (P1706), and scheduled service
destination (P521), resulting in around 1,500 violations in total.

###  3.6 Are Constraints Correct and Complete?

If the constraints are to be used as a driving force to improve the quality of
Wikidata, it is important that they are correct and complete. As shown in
Table 4, the majority of the constraints fit the data, which can be seen as an
indicator that the constraints are of good quality. Yet, we note that across
all constraint types, a small portion of the constraints yields a large
portion of violations.

The head of the distribution in Figure 4 reveals properties whose constraint
definitions are outdated. Table 5 lists those property constraints with large
(nearly 100%) violation ratios, which may point to discrepancies between the
constraints and the underlying data. For example, towards (P5051) expects
subjects to be instances of transport stop (Q548662), which is violated for
all its 64 instances. 28 of these instances have a type vein (Q9609) (e.g.,
external jugular vein (Q2512768)), and use the towards property to indicate
the direction blood flow of a vein in the human body (e.g., subclavian vein is
oriented towards the brachiocephalic vein). In this case, rather than fixing
each statement with a constraint violation manually, one could generalize the
constraint, i.e., enhance the type constraint for the towards property to
allow for instances of vein.

Table 6: Top classes (left) and properties (right) in the deprecated statements. Class | Count | Property | Count
---|---|---|---
infrared source (Q67206691) | 2,546,256 | instance of (P31) | 3,303,204
star (Q523) | 352,194 | proper motion (P2215) | 2,236,125
near-IR source (Q67206785) | 60,055 | parallax (P2214) | 2,159,860
astronomical radio source (Q1931185) | 43,618 | radial velocity (P2216) | 816,191
galaxy (Q318) | 35,768 | distance from Earth (P2583) | 461,113
Table 7: Violations within the removed statements for each type of constraint. constraint | mandatory | normal | suggestion
---|---|---|---
type | 763k/2.31M (33.04%) | 5.3M/34.87M (15.21%) | 920/2.29k (40.12%)
value type | 25.4k/211k (12.03%) | 198k/8.99M (22.06%) | 235/397 (59.19%)
IRS | 4.67k/1.28M (0.36%) | 192k/4.85M (3.97%) | 190k/6.01M (3.17%)
inverse | 37/345 (10.72%) | 177k/534k (33.13%) | 11.7k/160k (7.27%)
symmetric | 19/307 (6.19%) | 7.52M/10.85M (69.37%) | 5.05k/37.5k (13.47%)

###  3.7 What Statements Get Deprecated?

We investigate whether deprecated statements, as a soft alternative to
deletions, reveal different behavior compared to removed statements. Among the
10 million statements with deprecated rank in Wikidata, we observe that many
belong to the domain of Astronomy. This indicates that the decision between
removing and deprecating a statement largely depends on the community and the
domain.

Specifically, we found 10,040,256 deprecated statements. The top-5 properties
in deprecated statements are shown in Table 6. We observe that all frequently
deprecated properties (e.g., proper motion) belong to the domain of Astronomy,
and that large portion of the overall deprecations (around 90%) is expressed
with these first five properties. In addition, we observe that the deprecated
instance of statements describe membership of celestial objects, like infrared
source, star, and galaxy.

###  3.8 Are Constraint Violations Getting Fixed?

Our analysis reveals that Wikidata has millions of deleted statements and
constraint violations. Do these two sets overlap? We observe that many of the
removed statements violated a constraint, i.e., many of the removals coincide
with former violations, thereby improving the quality of Wikidata over time.

Specifically, out of the 2.31 million removed statements for which a mandatory
type constraint is defined, a third violated that constraint (Table 7). Most
of the former violations correspond to normal and suggested constraints.
Overall, we observe that the removed statements fixed millions of constraint
violations, including 6 million type violations and 7.5 million symmetric
violations.

Notably, constraints could have been fixed or violated through the addition
(instead of removal) of statements, which we are not considering in our work
and, as such, it is a limitation of our current analysis.

##  4 Recommendations

The knowledge in Wikidata is relatively reliable in comparison to other
general-domain KGs (Färber et al., 2018). Yet, our analysis reveals a variety
of quality aspects of Wikidata that can be improved going forward. Based on
our findings, we propose several recommended actions to include in the
interactive contributing environment of Wikidata. These recommendations are
intended to prevent low-quality statements from being added, as fixing them
later might take a large number of edits. The recommendations can complement
ongoing efforts by the Wikidata community to improve data quality based on
games and suggestions, aiming to make it easier for users and editors to find
and correct mistakes.

Integrate entity linking: To prevent introducing duplicate nodes, it would be
beneficial to provide suggestions for similar entities when these exist. For
instance, if the user is introducing a basketball player named “Michael
Jordan” who played for Chicago Bulls, the environment should inform the user
that a similar item is already present in Wikidata (with id Q41421).

Prevent type and value type violations: When an editor introduces a new
entity, its type should be coherent with the type and value type constraints
of its properties. When this is not the case, the editor should be warned
about a possible violation. Instead of adapting each new statement, the editor
may opt to suggest adapting the constraints themselves.

Introduce format guidelines for strings: Our analysis showed that a large
portion of the literal updates transform the literal between two semantically
equivalent forms. We propose having more precise formatting guidelines for
strings, aiming to adopt consistent naming conventions. For instance, a
guideline for initials of human names may dictate including a letter and a dot
(“Pamela C. Rasmussen” rather than “Pamela C Rasmussen”).

Complement missing data: Wikidata’s interactive editing environment should
propose that the editor makes complete edits, i.e., edits that satisfy the
constraints of the affected properties. One way to achieve this would be to
suggest that the edits satisfy the constraints of types item-requires-
statement, symmetric, and inverse, by either adding the full set of statements
that satisfy the constraint, or removing the one violating it. A complementary
idea is to include a link prediction method, like HINGE (Rosso et al., 2020)
or StarE (Galkin et al., 2020), in order to suggest missing statements based
on probabilistic graph patterns.

Fix statements retroactively: Given the large number of existing constraint
violations, it is important to help the Wikidata community to fix them. One
possibility is to leverage Wikidata’s Distributed games171717https://wikidata-
game.toolforge.org/distributed/# approach and create games to help editors
efficiently validate and fix the constraints. A good starting point for this
are the property constraints with large violation ratios, which were detected
through our analysis in Table 5 and Figure 4. An alternative approach, based
on our finding in Section 3.6, is to fix violations automatically with the
expectation that after the automatic fixes there will be fewer violations, and
it would be more efficient to fix the errors introduced by the automatic fixes
than the original ones. Another option is to employ methods that automatically
detect errors in KGs (Yao and Barbosa, 2021).

##  5 Related Work

The quality of Knowledge Graphs has been studied in existing literature. Chen
et al. (2019) proposed a framework for evaluating the quality of KGs,
consisting of dimensions that quantify their fitness for downstream
applications. Similarly, quality metrics from 28 prior papers are surveyed by
Piscopo and Simperl (2019), and grouped into three dimensions: intrinsic
(i.e., accuracy, trustworthiness, and consistency of entities), contextual
(i.e., completeness and timeliness of resources), and representation (i.e.,
understanding, interoperability of entities). Our quality indicators are
orthogonal to these metrics, as we consider the consensus of the community for
them. In addition, our methods go further by proposing an approach to
efficiently evaluate some of the metrics proposed by Piscopo and Simperl
(2019).

Many of the metrics proposed by Piscopo and Simperl (2019) are covered by
Färber et al. (2018), who compare the quality of modern KGs: Wikidata, YAGO,
DBpedia, FreeBase, and OpenCyc. Piscopo and Simperl (2018) evaluated the
quality of Wikidata from an ontological perspective, using indicators related
to quantitative measures of classes and instances (e.g., number of instances
and number of properties) and of the richness of classes, relations, and
properties (e.g., inheritance richness and class hierarchy depth). Prior work
has also investigated whether the quality of a knowledge statement in Wikidata
depends on the engagement of its editor (leader or contributor) (Piscopo et
al., 2017b; Piscopo and Simperl, 2018), or the knowledge provenance indicated
through the references of a statement (Piscopo et al., 2017a). Instead, our
work performs a systematic analysis of constraint violations, and assesses
whether the removal of statements by the community reduces violations.

Wikidata includes several tools that monitor, analyze, and enforce aspects of
quality. The primary sources tool (PST) facilitates a curation workflow for
uploading data into
Wikidata.181818https://www.wikidata.org/wiki/Wikidata:Primary_sources_tool#References
The Objective Revision Evaluation Service (ORES) scores revisions
automatically, aiming to detect edits which represent
vandalisms.191919https://www.wikidata.org/wiki/Wikidata:ORES Recoin (“Relative
Completeness Indicator”) (Balaraman et al., 2018) extends Wikidata entity
pages with information about the relative completeness of the information.
Relative completeness is computed by comparing the available information for
an entity against other similar entities. Property constraint pages define
existing property constraints and report number of violations for a single
dump.202020https://www.wikidata.org/wiki/Help:Property_constraints_portal Our
analysis complements the constraint violations reported by Wikidata’s pages,
by providing in-depth insights about these violations, and abstracting them
into findings and recommendations.212121For more information about data
quality tools integrated in Wikidata, we refer the reader to:
https://www.wikidata.org/wiki/Wikidata:WikiProject_Data_Quality and
https://docs.google.com/presentation/d/1rwjqzPaHTsXNNqDc2Op1-qSbcFyaFwOSnkEkStp5L3E/edit.

Recently, Wikidata has started moving beyond individual property constraints,
representing a higher-level notion of quality in the form of shapes that are
meant to provide norms of well-formedness for sub-graphs describing concepts
of interest (Thornton et al., 2019), e.g.,
human.222222https://www.wikidata.org/wiki/EntitySchema:E10 These shapes are
collected as
Schemas.232323https://www.wikidata.org/wiki/Wikidata:WikiProject_Schemas Each
schema defines the desired sub-graph topology describing a given concept,
using ShEx shape expressions (Thornton et al., 2019). Schemas are defined
through consensus among specific communities (e.g., molecular biology,
software engineering, etc.) interested in standardizing concepts relevant to
them.242424https://www.wikidata.org/wiki/Wikidata:Database_reports/EntitySchema_directory
We have not addressed the analysis of Wikidata at this level of abstraction,
but the approach described in this work can be naturally extended in this
direction. A similar observation can be made about prior work that encodes
Wikidata constraints based on the multi-attributed relational structures
(MARS) (Patel-Schneider and Martin, 2020), a formal data model for generalized
property graphs devised by Marx et al. (2017).

Recognizing the complexity of the class and type hierarchy in Wikidata, the
authors of YAGO4 hand-crafted a new, principled type hierarchy for Wikidata,
specifying constraints in SHACL252525https://www.w3.org/TR/shacl/ and OWL
(McGuinness et al., 2004); and running scripts to synthesize YAGO by ingesting
the data from Wikidata and processing the SHACL expressions. YAGO4 defines
constraints on domain and range, disjointness, functionality, and cardinality.
The authors report that enforcing these constraints leads to a removal of 132M
statements from Wikidata, i.e., 28% of all facts. The constraints defined by
YAGO4 overlap partially with the constraints in Wikidata studied in this
paper. Subsequent work should compare the findings from validating constraints
in YAGO4 and Wikidata, and it should generalize the in-depth analysis done in
this paper to other KGs like YAGO4.

Rashid et al. (2019) investigated the evolution of 10 classes from DBpedia
over 11 of its releases, measuring aspects of: persistence, consistency, and
completeness. This effort resembles our community-based indicator, but it
reports analysis over a small data subset, a smaller knowledge graph, and
fewer dumps. The goal of Rashid et al. (2019) is to identify potential
problems in the data processing pipeline, which is orthogonal to our goal of
detecting low-quality statements in the knowledge graph itself.

Other work has focused on data validation in KGs. The LOD Laundromat (Beek et
al., 2014) is a large-scale infrastructure that can validate and clean
syntactic errors that do not fit the formal specification of RDF, such as bad
encoding, undefined URI prefixes, and premature end-of-file markers. Beek et
al. (2018) devise a toolchain for analyzing of the quality of literals in LOD
Laundromat’s data collection, proposing to automatically improve their value
canonization and language tagging. Our work focuses on errors that cannot be
detected by methods that check the syntactic validity of typed literals, like
illegal dates, and is thus orthogonal to such prior work.

Recent work has assessed quality for specific domains. For instance, Turki et
al. (2020) report an analysis using ShEx expressions to assess the quality of
COVID-19 knowledge in Wikidata. This analysis is more comprehensive than the
one reported in our paper, but with a much more limited scope and less
generalizable, reflecting the consensus of a specialized community.

Finally, our work relates to efforts that assess the quality of voluntary
contributions to large knowledge bases, like Wikipedia (Wilkinson and
Huberman, 2007; Raman et al., 2020) and Open Street Maps (Mooney and Corcoran,
2012; Fonte et al., 2017). The quality indicators and findings in these works
may inspire future research into the quality of large “wisdom of the
crowd”-based KGs like Wikidata.

##  6 Conclusions

This paper studies the quality of Wikidata by proposing three quality
indicators based on statements that have been 1) permanently removed; 2)
deprecated; or 3) violate constraints defined by the community. Our analysis
reveals that, while Wikidata is becoming a KG of increasing quality (removing
duplicate entities, fixing modeling errors, and removing constraint
violations) there is still room for improvement for preventing entity
duplication and constraint violations, having consistent guidelines for
literals, and completing missing data.

Our findings may complement ongoing efforts by the Wikidata community to
improve data quality based on games and suggestions, aiming to make it easier
for users to find and correct mistakes. In fact, we are initiating a
discussion on how to integrate our methods, findings, and recommendations into
Wikidata’s infrastructure. Future work will expand our constraint analysis to
additional constraint types and properties; investigate the quality of
Wikidata over time, its relation to contributor profiles (Piscopo and Simperl,
2018); and will expand our findings by considering additional qualifiers and
references (Piscopo et al., 2017a).

## Acknowledgements

This material is based on research sponsored by Air Force Research Laboratory
under agreement number FA8750-20-2-10002. The U.S. Government is authorized to
reproduce and distribute reprints for Governmental purposes notwithstanding
any copyright notation thereon. The views and conclusions contained herein are
those of the authors and should not be interpreted as necessarily representing
the official policies or endorsements, either expressed or implied, of Air
Force Research Laboratory or the U.S. Government. Daniel Schwabe was partially
supported by grant 309808/2017-0 from CNPq - Brazil.

## References

  * Balaraman et al. (2018) Balaraman, V., Razniewski, S., Nutt, W., 2018.  Recoin: relative completeness in wikidata, in: Companion Proceedings of the The Web Conference 2018, pp. 1787–1792.
  * Beek et al. (2018) Beek, W., Ilievski, F., Debattista, J., Schlobach, S., Wielemaker, J., 2018.  Literally better: Analyzing and improving the quality of literals.  Semantic Web 9, 131–150.
  * Beek et al. (2014) Beek, W., Rietveld, L., Bazoobandi, H.R., Wielemaker, J., Schlobach, S., 2014.  Lod laundromat: a uniform way of publishing other people’s dirty data, in: International semantic web conference, Springer. pp. 213–228.
  * Boneva et al. (2019) Boneva, I., Dusart, J., Alvarez, D.F., Gayo, J.E.L., 2019\.  Shape designer for shex and shacl constraints, in: ISWC 2019-18th International Semantic Web Conference.
  * Chen et al. (2019) Chen, H., Cao, G., Chen, J., Ding, J., 2019.  A practical framework for evaluating the quality of knowledge graph, in: China Conference on Knowledge Graph and Semantic Computing, Springer. pp. 111–122.
  * Dong et al. (2014) Dong, X., Gabrilovich, E., Heitz, G., Horn, W., Lao, N., Murphy, K., Strohmann, T., Sun, S., Zhang, W., 2014.  Knowledge vault: A web-scale approach to probabilistic knowledge fusion, in: Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 601–610.
  * Färber et al. (2018) Färber, M., Bartscherer, F., Menne, C., Rettinger, A., 2018\.  Linked data quality of dbpedia, freebase, opencyc, wikidata, and yago.  Semantic Web 9, 77–129.
  * Fonte et al. (2017) Fonte, C.C., Antoniou, V., Bastin, L., Estima, J., Arsanjani, J.J., Bayas, J.C.L., See, L., Vatseva, R., 2017\.  Assessing vgi data quality.  Mapping and the citizen sensor , 137–163.
  * Galkin et al. (2020) Galkin, M., Trivedi, P., Maheshwari, G., Usbeck, R., Lehmann, J., 2020.  Message passing for hyper-relational knowledge graphs.  arXiv preprint arXiv:2009.10847 .
  * Garijo and Szekely (2021) Garijo, D., Szekely, P., 2021\.  Wikidata removed statements from Oct 2014 - Jan 2021\.  doi:10.5281/zenodo.4686805.
  * Ilievski et al. (2020) Ilievski, F., Garijo, D., Chalupsky, H., Divvala, N.T., Yao, Y., Rogers, C., Li, R., Liu, J., Singh, A., Schwabe, D., Szekely, P., 2020\.  Kgtk: a toolkit for large knowledge graph manipulation and analysis, in: International Semantic Web Conference, Springer, Cham. pp. 278–293.
  * Marx et al. (2017) Marx, M., Krötzsch, M., Thost, V., 2017.  Logic on mars: Ontologies for generalised property graphs., in: IJCAI, pp. 1188–1194.
  * McGuinness et al. (2004) McGuinness, D.L., Van Harmelen, F., et al., 2004\.  Owl web ontology language overview.  W3C recommendation 10, 2004\.
  * (14) Möller, C., Lehmann, J., Usbeck, R., .  Survey on english entity linking on wikidata .
  * Mooney and Corcoran (2012) Mooney, P., Corcoran, P., 2012\.  Characteristics of heavily edited objects in openstreetmap.  Future Internet 4, 285–305.
  * Patel-Schneider and Martin (2020) Patel-Schneider, P.F., Martin, D., 2020\.  Wikidata on mars.  arXiv preprint arXiv:2008.06599 .
  * Piscopo et al. (2017a) Piscopo, A., Kaffee, L.A., Phethean, C., Simperl, E., 2017a.  Provenance information in a collaborative knowledge graph: an evaluation of wikidata external references, in: International semantic web conference, Springer. pp. 542–558.
  * Piscopo et al. (2017b) Piscopo, A., Phethean, C., Simperl, E., 2017b.  What makes a good collaborative knowledge graph: Group composition and quality in wikidata, in: SocInfo.
  * Piscopo and Simperl (2018) Piscopo, A., Simperl, E., 2018\.  Who models the world? collaborative ontology creation and user roles in wikidata 2.  doi:10.1145/3274410.
  * Piscopo and Simperl (2019) Piscopo, A., Simperl, E., 2019\.  What we talk about when we talk about wikidata quality: a literature survey, in: Proceedings of the 15th International Symposium on Open Collaboration, pp. 1–11.
  * Raman et al. (2020) Raman, N., Sauerberg, N., Fisher, J., Narayan, S., 2020\.  Classifying wikipedia article quality with revision history networks, in: Proceedings of the 16th International Symposium on Open Collaboration, pp. 1–7.
  * Rashid et al. (2019) Rashid, M., Torchiano, M., Rizzo, G., Mihindukulasooriya, N., Corcho, O., 2019.  A quality assessment approach for evolving knowledge bases.  Semantic Web 10, 349–383.
  * Rosso et al. (2020) Rosso, P., Yang, D., Cudré-Mauroux, P., 2020.  Beyond triplets: hyper-relational knowledge graph embedding for link prediction, in: Proceedings of The Web Conference 2020, pp. 1885–1896.
  * Schuler (2005) Schuler, K.K., 2005.  Verbnet: A broad-coverage, comprehensive verb lexicon .
  * Shenoy et al. (2021a) Shenoy, K., Ilievski, F., Garijo, D., 2021a.  Constraint violation summaries (Dump: Dec 7th, 2020).  URL: https://doi.org/10.5281/zenodo.5121276, doi:10.5281/zenodo.5121276.
  * Shenoy et al. (2021b) Shenoy, K., Ilievski, F., Garijo, D., 2021b.  usc-isi-i2/wd-quality: First notebook release.  URL: https://doi.org/10.5281/zenodo.5119983, doi:10.5281/zenodo.5119983.
  * Shenoy et al. (2021c) Shenoy, K., Ilievsky, F., Szekely, P., 2021c.  Wikidata deprecated statements by jan 2021.  URL: https://doi.org/10.5281/zenodo.5120117, doi:10.5281/zenodo.5120117.
  * Surowiecki (2004) Surowiecki, J., 2004.  The wisdom of crowds : why the many are smarter than the few and how collective wisdom shapes business, economies, societies, and nations.  Doubleday, New York.
  * Tanon et al. (2020) Tanon, T.P., Weikum, G., Suchanek, F., 2020.  Yago 4: A reason-able knowledge base, in: European Semantic Web Conference, Springer. pp. 583–596.
  * Thornton et al. (2019) Thornton, K., Solbrig, H., Stupp, G.S., Gayo, J.E.L., Mietchen, D., Prud’Hommeaux, E., Waagmeester, A., 2019.  Using shape expressions (shex) to share rdf data models and to guide curation with rigorous validation, in: European Semantic Web Conference, Springer. pp. 606–620.
  * Turki et al. (2020) Turki, H., Jemielniak, D., Taieb, M.A.H., Gayo, J.E.L., Aouicha, M.B., Banat, M., Shafee, T., Prud’Hommeaux, E., Lubiana, T., Das, D., Mietchen, D., 2020.  Using logical constraints to validate information in collaborative knowledge graphs: a study of COVID-19 on Wikidata.  doi:10.5281/zenodo.4445363.
  * Vrandečić and Krötzsch (2014) Vrandečić, D., Krötzsch, M., 2014\.  Wikidata: a free collaborative knowledgebase.  Communications of the ACM 57, 78–85.
  * Wilkinson and Huberman (2007) Wilkinson, D.M., Huberman, B.A., 2007\.  Cooperation and quality in wikipedia, in: Proceedings of the 2007 international symposium on Wikis, pp. 157–164.
  * Yao and Barbosa (2021) Yao, P., Barbosa, D., 2021.  Typing errors in factual knowledge graphs: Severity and possible ways out.  arXiv preprint arXiv:2102.02307 .

##  Appendix A Sample instantiated query template

The snippet below represents the KGTK queries that encode the item requires
statement constraints (IRS) for property P1321 (place of origin (Switzerland))
in Wikidata.262626https://www.wikidata.org/wiki/Property:P1321 The property
has two IRS constraints: 1) each item of the property should be (P31) a human
(Q5) and 2) its country of citizenship (P27) should be Switzerland (Q39).
There is a single exception to this rule, the person Hans von Flachslanden
(Q1583384). The code of the query below is generated automatically with our
framework. Comments have been added (with _"#"_) to explain the different
parts of the query.

    kgtk query  # Query to retrieve valid entities
      -i claims.P1321.tsv  # Statements with property P1321
         claims.P31.tsv    # Statements with property P31
         claims.P27.tsv    # Statements with property P27
      --match
        ’P1321: (node1)-[nodeProp]->(node2),
         P31: (node1)-[]->(node2_P31),
         P27: (node1)-[]->(node2_P27)’
      --where ’node2_P31 in ["Q5"]  # subject has to be
                                    # human (Q5)
         and node2_P27 in ["Q39"]’  # subject should live in
                                    # Switzerland (Q39)
      --return ’distinct nodeProp.id, node1 as ‘node1‘,
        nodeProp.label as ‘label‘,
        node2 as ‘node2‘’
      -o claims.P1321.correct_wo_exceptions.tsv
      --graph-cache cache.db;

    kgtk ifnotexists # Now we calculate violations
                             # of P1321.
      -i claims.P1321.tsv
      --filter-on claims.P1321.correct_wo_exceptions.tsv
      -o claims.P1321.incorrect_wo_exceptions.tsv

    kgtk query # Exclude exceptions, i.e.,
                       # Hans von Flachslanden (Q1583384)
      -i claims.P1321.incorrect_wo_exceptions.tsv
      --match
        ’(node1)-[]->()’ --where ’node1 in ["Q1583384"]’
      -o claims.P1321.incorrect_w_exceptions.tsv
      --graph-cache cache.db;

    kgtk ifnotexists  # Filter exceptions from
                              # violations file
      -i claims.P1321.incorrect_wo_exceptions.tsv
      --filter-on claims.P1321.incorrect_w_exceptions.tsv
      -o claims.P1321.incorrect.tsv;

    kgtk cat # Aggregate correct results.
      -i claims.P1321.correct_wo_exceptions.tsv
         claims.P1321.incorrect_w_exceptions.tsv
      -o claims.P1321.correct.tsv


Temporal effects in trend prediction: identifying the most popular nodes in
the future

Yanbo Zhou1 An Zeng2 Wei-Hong Wang1

1 College of Computer Science and Technology, Zhejiang University of
Technology, Hangzhou, P. R. China
2 School of Systems Science, Beijing Normal University, Beijing, P. R. China
$\ast$ E-mail: Corresponding<EMAIL_ADDRESS>
## Abstract

Prediction is an important problem in different science domains. In this
paper, we focus on trend prediction in complex networks, i.e. to identify the
most popular nodes in the future. Due to the preferential attachment mechanism
in real systems, nodes’ recent degree and cumulative degree have been
successfully applied to design trend prediction methods. Here we took into
account more detailed information about the network evolution and proposed a
temporal-based predictor (TBP). The TBP predicts the future trend by the node
strength in the weighted network with the link weight equal to its exponential
aging. Three data sets with time information are used to test the performance
of the new method. We find that TBP have high general accuracy in predicting
the future most popular nodes. More importantly, it can identify many
potential objects with low popularity in the past but high popularity in the
future. The effect of the decay speed in the exponential aging on the results
is discussed in detail.

## Introduction

The emergence of online social media and rich user-generated content bring the
information overload problem. The online content has become increasingly
abundant and immediately available, and users cannot go through every piece of
information to find the high quality ones [1]. These high quality source, in
general, have formidable power to impact opinions, culture, and policy, as
well as advertising profit. Thus they usually attract a lot of attention and
become eventually popular. The rapid development of the Internet results in
the availability of a huge amount of data with time information, making it
possible to study the popularity dynamic of the online content. It was found
that the popularity of various pieces of content on the Web, like news [2],
Twitter [3], blog posts [4], videos [5, 6], posts in online discussion forums
[7] and product reviews [8], vary significantly on temporal scales. In this
context, the early identification of the eventual popular content becomes an
important problem [9]. It cannot only improve the user experience as the
prediction save their searching time for high quality contents among unpopular
ones, but also bring commercial profit for the online vendor as it helps them
better manage their inventory.

Although the preferential attachment (PA) is a success in explaining the
power-law distribution that widely found in real systems [10], it performs not
satisfying enough when applied to predict the future popularity (or degree) of
nodes. For example, it was found in the citation networks that some papers can
attract significantly more citations than the prediction from PA [11, 12]. The
ability of a node to attract new links is found to decay exponentially with
time, both in citation networks [13] and information access [14]. Moreover,
temporal analysis of the popularity dynamics of online content in Wikipedia
[15] and micro blog[16] shows the burst pattern. An extensive study of how the
content’s popularity grows and fades over time in online media has been
presented in ref. [17]. Besides the experimental study of the temporal
dynamic, some possible mechanisms that may contribute to the experimental
finding are proposed, such as relevance and time decay [13], random popularity
shifts [15] and human dynamics [5]. All these studies have shown that the high
cumulative degree of nodes is not a guarantee for large degree increase in the
future.

In this paper, we focus on the trend prediction in complex networks, i.e. to
identify the most popular nodes in the future. In the literature, there are
some existing methods for this problem especially for a certain application
field [18, 19, 20, 21]. For instance, in the popular online service _Digg.com_
, the initial growth popularity has been used to predict its later popularity
[19]. Popularity-based predictor has been designed for trend prediction and
its performance is shown to be further enhanced if the user social network is
incorporated [20]. In this paper, we introduce a temporal-based predictor
(TBP) which takes advantage of the time decay effect found in many empirical
works. The validation of the method is conducted in three time-stamped data
sets. The results show that the prediction precision is remarkably higher than
that of PA. In addition, the new method is especially effective in identifying
the potential nodes with low popularity in the past but high popularity in the
future.

## Materials and Methods

The system we considered in this paper can be modeled by the bipartite network
which consists of a set of users $U$ and a set of objects $O$. We use Latin
letters for users and Greek letters for objects to distinguish them. A
bipartite network can be represented by an adjacency matrix $A$, where
elements $A_{i\alpha}$ are equal to 1 if user $i$ has collected object
$\alpha$ and 0 otherwise. We consider snapshots of these networks at different
time stamps by taking into account only the links established before a given
time $t$, and we use $A(t)$ to denote the adjacency matrix at time $t$. The
number of objects collected by user $i$ and the number of users who collected
object $\alpha$ at time $t$ ($i.e.$, user degree and object degree) are
computed as $k_{i}(t)=\sum_{\alpha}A_{i\alpha}(t)$ and
$k_{\alpha}(t)=\sum_{i}A_{i\alpha}(t)$, respectively.

The popularity increase of object $\alpha$ in future $T_{F}$ time steps (i.e.
the future time window) is then

$\Delta{k_{\alpha}(t,T_{F})}=k_{\alpha}(t+T_{F})-k_{\alpha}(t).$ (1)

For a suitably chosen value of $T_{F}$, this quantity can measure the temporal
interest in object $\alpha$. The main goal of trend prediction in this paper
is to identify the most popular objects in the future. To this end, we define
a testing time $t$ and a future time window of length $T_{F}$, and rank all
objects according to their popularity increase $\Delta{k_{\alpha}(t,T_{F})}$.
This ranking is considered as the true ranking of popularity in the future. A
generic predictor will make use of the information before $t$ and assign
prediction scores $s_{\alpha}$ to all objects. These scores will be mapped
into a predicted ranking. In general, the higher overlap of the predicted
ranking and the true ranking, the better the predictor is.

### Popularity-based Predictor

Preferential attachment is a well-known mechanism of network evolution which
assumes that the probability a node to attract a new link is proportional to
its cumulative degree. In trend prediction, this means that objects which are
popular at time $t$ are expected to have better chances to attract new links
from users. This implies that the cumulative degree of an object
$k_{\alpha}(t)$ is a good predictor of its future popularity increase.
Considering the decaying interest in objects, the prediction scores can be set
as the recent popularity of objects. The prediction score of an object at time
$t$ can be calculated by $\Delta{k}_{\alpha}(t,T_{P})$ where $T_{P}$ is the
length of the considered history. Recently, a popularity-based predictor (PBP)
[20] has been proposed to combine the predictor $k_{\alpha}(t)$ and
$\Delta{k}_{\alpha}(t,T_{P})$. PBP has a tunable parameter $\lambda\in[0,1]$
to make the new predictor change smoothly from $k_{\alpha}(t)$ to
$\Delta{k}_{\alpha}(t,T_{P})$. Mathematically, the prediction score of PBP is
computed as

$s_{\alpha}(t,T_{P})=(1-\lambda)k_{\alpha}(t)+\lambda\Delta{k}_{\alpha}(t,T_{P})=k_{\alpha}(t)-\lambda
k_{\alpha}(t-T_{P}).$ (2)

This predictor simplifies to the total popularity method when $\lambda=0$ and
to the recent popularity method when $\lambda=1$.

### Temporal-based predictor

The popularity-based predictor in fact considers all the recent popularity of
objects, but weakens the influence of links an object received before
$t-T_{P}$. In the literature, it has been found that the interest toward
individual objects vanishes exponentially with time in some case [13, 22].
Therefore, it is too arbitrary to simply divide the time into two segments in
the popularity-based predictor, as it may lose the detailed temporal
information of real networks.

To make better use of the temporal information for trend prediction, we
proposed a temporal-based predictor (TBP) in this paper. In TBP, we consider
the mechanism that the influence of a link exponentially decays with time. An
aging function is accordingly introduced to calculate the prediction scores:

$s_{\alpha}(t)=\sum_{i}{A_{i\alpha}(t)e^{\gamma(T_{i\alpha}-t)}},$ (3)

where $T_{i\alpha}$ denotes the time at which user $i$ select object $\alpha$.
$\gamma$ is a positive parameter which controls the decay speed. A larger
$\gamma$ indicates a faster decay, and $\gamma=0$ corresponds to the
cumulative popularity without any decay. TBP preserves all the detailed
temporal information in the network. By adjusting $\gamma$, we can study the
temporal effects in the prediction of the future popularity.

## Data Description

To test the performance of TBP, we use three distinct real data sets:
MovieLens, Netflix and Facebook in this paper. Movielens and Netflix data sets
contain movie ratings, and Facebook data set contains users’ wall post
relationships. MovieLens is provided by GroupLens project at University of
Minnesota (www.grouplens.org). We use their 10 million ratings data set. Each
user in MovieLens data set has at least 20 ratings. Netflix is a huge data set
released by the DVD rental company Netflix for its Netflix Prize
(www.netflixprize.com). The original data has 480189 users, 17770 objects and
100480507 ratings. Since the original Movielens and Netflix data sets are
large, we extracted a small subset from each of them by randomly choosing some
users who have rated at least 20 movies and took all movies they had rated.
For both Movielens and Netflix, the ratings are given on the integer scale
from 1 to 5 (from worst to best). We here only consider the ratings higher
than 2 as a link. The final data consists of 5000 users, 7533 movies, and
864581 links in Movielens and 4960 users, 16599 movies, and 1249058 links in
Netflix. Facebook data set contains a list of all the wall posts from the
Facebook New Orleans networks [23, 24, 25]. A link from one user to another
corresponds that the user post on another user’s wall. As the Facebook network
is a unipartite directed network, here we mapped it to a bipartite network
with a set of users and a set of users’ walls (objects). If a user has posted
on a wall, there will be a link between the user and the wall. The original
data has $42390$ users , $39986$ objects and $876993$ links. Since user may
written on his own wall, we remove these links to eliminate self-influence.
The final data consists of $40981$ users, $38143$ objects and $855542$ links.
For all of these three data sets, the time is counted by days. The
characteristics of these data sets are summarized in table 1. All these three
data sets are available from the Koblenz Network Collection [26], and they are
all free to use even for commercial purposes.

## Evaluation Metrics

We apply three metrics to give quantitative measurements of the predictors’
performance: AUC, precision and novelty.

As the main point of this paper is to predict which objects will be popular in
the future, only the top part of the ranking list should be considered when
evaluating the performance of the predictors. We thus use a standard measure
in information filtering literature named AUC [27], which evaluates a ranking
list by calculating the relative position of its top $n$ objects. We select
the top $n$ objects in the real future as a group of benchmark objects, and
denoted it as set $B$. The other objects are in the complement group of $B$,
which denoted as $B^{\prime}$. Then the AUC is calculated as

$AUC=\frac{1}{|B||B^{\prime}|}\sum_{\alpha\in B}\sum_{\beta\in
B^{\prime}}I(s_{\alpha},s_{\beta}),$ (4)

where

$I(s_{\alpha},s_{\beta})=\begin{cases}0,\qquad\mathrm{if}\quad
s_{\alpha}<s_{\beta}\\\ 0.5,\quad\mathrm{if}\quad s_{\alpha}=s_{\beta}\\\
1,\qquad\mathrm{if}\quad s_{\alpha}>s_{\beta}\par\end{cases}.$ (5)

AUC equals to one when all benchmark objects are ranked higher than the other
objects, while AUC=0.5 corresponds to a completely random object ranking list.

Another evaluation matric is called precision. It is defined as the fraction
of objects in the top $n$ places of the estimated ranking that appear also in
the top $n$ places of the true ranking [28]. The precision of the predictor is
defined as $P_{n}=D_{n}/n$, where $D_{n}$ indicates the number of common
objects in the top $n$ places of the predicted ranking and the true ranking.
It lies in the range [0, 1], the higher the better.

It is often the case that objects popular in the future time window
$(t,t+T_{F}]$ were already popular in the past. Successful prediction of those
objects can contribute to precision $P_{n}$. However, prediction of these
objects brings much less benefit to users than the prediction of genuinely
”new entries”, i.e. objects that were missing in top $n$ in the past but they
appear there in the future time window. We label the true number of those
objects as $E_{n}$ and the number of those successfully identified by the
predicted ranking as $C_{n}$, respectively. The rate of correct prediction of
these new entries is $Q_{n}=C_{n}/E_{n}$. This allows us to measure how well a
predictor is able to identify the potential objects. Here, we name $Q_{n}$ as
novelty.

## Results

To obtain the final evaluation of the predictors’ performance, we average
results over 10 randomly selected $t$ for each data sets. To make sure that
there is enough history information, $t$ is set as at least one year later
than the first record in each data set. As all the predictors we considered in
this paper are based on objects’ history, we only consider the objects with at
lest one link before the testing date $t$.

Figure 1 shows the performance of the TBP under different $\gamma$ in
Movielens, Netflix and Facebook data sets, respectively. $T_{F}$ is set as 30
days for all there data sets. Different $n$ values are given for all metrics.
The results show that the influence of $\gamma$ doesn’t change by $n$. When
$\gamma=0$ (equivalent to cumulative degree predictor), the AUC and $P_{n}$
are relatively small and $Q_{n}=0$ for all data sets. This indicates that PA
have little efficacy in predicting the future popularity. A small $\gamma$ (a
relatively slow time decay) can significantly increase the prediction
performance, especially for $Q_{n}$. The high value of $Q_{n}$ indicates that
the temporal-based predictor has a great power to identify ”new objects” which
are not yet popular. A too large $\gamma$ will decrease the performance, and
we can get the best performance of TBP for all data sets by changing $\gamma$.
We denote $\gamma^{*}$ as the parameter resulting in the highest $P_{n}$
value. It is clear that the performance of TBP with parameter $\gamma^{*}$ is
remarkably higher than that of PA (i.e. $\gamma=0$ in TBP).

Table 2 shows the performance of TBP and PBP for the three data sets. The
parameter for each predictor is selected as the one corresponding to the
highest $P_{n}$ value. From the results, we could find that TBP has a better
performance for most evaluation metrics. The best $\lambda$ value for PBP is
0.98 for both Movielens and Netflix data set and 0.93 for Facebook data set,
which indicates that the links an object received long time ago has a small
influence on its future popularity. Unlike the arbitrarily dividing the time
into two segments in PBP, TBP uses an exponential decay function which can
future improve the prediction performance.

We set a rank change value for each object as $dr=r_{f}-r_{p}$, where $r_{f}$
is the real rank in the near future and $r_{p}$ is the rank by a predictor.
$dr=0$ indicates the prediction rank is echo to the real rank in the near
future, and the predictor has perfect performance; $dr<0$ indicates the
predictor underestimate the object’s popularity. $dr>0$ indicates the
predictor overrate the object’s popularity. To test how different predictors
influence the rank of the top objects in the future, we plot figure 2 to show
the correlation of $dr$ with these objects’ degree rank $r_{k}$ in the testing
time under different predictors and parameters. This figure only considers the
top 100 objects in the $T_{F}$ window. The parameters $\lambda$ for PBP are
set as the one corresponding to the highest $P_{n}$ value. The parameters
$\gamma^{*}$ and $\gamma=1$ are also selected for TBP in figure 2. These
objects are ranked in the top 100 positions in the near future, but their
history popularity has a board distribution. Both TBP and PBP with the best
parameter can reduce the absolute value of $dr$, which makes these predictors
have better performance in predicting future popularity. Compered with PBP,
TBP is better at improving the rank of objects that have high $r_{k}$ but
ranked in top place in the future. When $\gamma=1$ in TBP, it is clear that
the absolute value of rank difference $d_{r}$ of the objects that have high
$r_{k}$ becomes smaller than the case with $\gamma^{*}$, but the absolute
value of rank difference $d_{r}$ of objects with lower $r_{k}$ becomes larger.
That may be due to the fact that parameter $\gamma$ can give less rank score
to the objects that are popular in the past, and then improve the rank of the
objects that are not popular in the past. The higher the parameter $\gamma$
is, the more obvious this influence is.

A small $T_{F}$ aims to predict objects’ popularity in the short term while a
large $T_{F}$ requires to predict the trend in long term. Therefore, we test
the performance of the predictors under different $T_{F}$. Figure 3 shows the
performance of the TBP and PBP as a function of the future time window
$T_{F}$. The parameters corresponding to the highest $P_{n}$ value for each
predictors at each $T_{F}$ point are selected. For PBP, $T_{P}$ is set as the
same length of $T_{F}$. Compared with PBP, it is clear that TBP has a better
prediction performance for all $T_{F}$ value. For all data sets, the precision
$P_{n}$, novelty $Q_{n}$ and AUC of the predictors increase substantially with
$T_{F}$ when $T_{F}$ is very small. This is because there is a lot of noise
when $T_{F}$ is too small. However, the precision decreases with $T_{F}$ while
$T_{F}$ becomes larger. This may because the predicted popularity becomes
outdated for larger $T_{F}$ time.

As we know, $\gamma$ can control the decay speed of the influence of the old
links. For different prediction time interval $T_{F}$, the best parameter
$\gamma^{*}$ may be different. Figure 4 shows the relationship of $\gamma^{*}$
with $T_{F}$. One could find that, the larger the $T_{F}$ length, the smaller
the $\gamma^{*}$ value. That means for a shorter $T_{F}$ prediction, the
objects’ recent popularity matters more. While for a larger $T_{F}$ interval
prediction, longer historical popularity should be considered.

## Discussion

To summarize, we proposed a temporal-based predictor (TBP) in this paper, and
studied the performance of TBP in trend prediction. The basic idea of TBP is
to introduce an exponentially time decay to predict objects’ future
popularity. We make use of three metrics to evaluate the predictor’s
performance: $P_{n}$, $Q_{n}$ and AUC. We found that the parameter $\gamma$,
which controls the speed of the time decay, can give less rank score to the
objects that are popular in the past, and accordingly improve the rank of the
objects that are not popular in the past. The higher $\gamma$ is, the more
obvious of this influence is. Thus, TBP has a higher ability to detect ”new
entries” that have a lower cumulative popularity but a higher future
popularity, and promote these objects to the front of the predicted ranking
list. Compared with PBP, TBP has a higher ability to detect the objects that
will be popular in the future with different future length $T_{F}$.

Ranking is one of the most important and fundamental method to solve
information over load problem. The study of the popularity dynamic of online
information gives us some inspiration to solve the trend prediction problem.
This is a very practical issue. In this paper, we studied the links’ temporal
effects on objects’ future popularity. This study is based on the experimental
finding that the ability of a node to attract new links vanishes exponentially
with time. Besides time, there are a lot of other elements that can influence
the dynamic of popularity, such as human dynamics, links heterogeneity, and
external influence. Introducing the influence of these elements may future
improve the performance of trend predictor. In our future studies, we will
focus on improving the performance of the trend predictors with the help of
both empirical observations and theoretical analysis.

## Acknowledgments

## References

  * 1. Simon HA (1971) Designing organizations for an information-rich world.  Computers, communications, and the public interest 72: 37.
  * 2. Szabo G, Huberman BA (2010) Predicting the popularity of online content.  Communications of the ACM 53: 80.
  * 3. Asur S, Huberman BA, Szabo G, Wang C (2011) Trends in social media: persistence and decay.  In: ICWSM.
  * 4. Kumar R, Novak J, Raghavan P, Tomkins A (2005) On the bursty evolution of blogspace.  World Wide Web 8: 159.
  * 5. Crane R, Sornette D (2008) Robust dynamic classes revealed by measuring the response function of a social system.  Proceedings of the National Academy of Sciences 105: 15649.
  * 6. Figueiredo F, Fabrício B, Jussara AM (2011) The tube over time: characterizing popularity growth of youtube videos.  In: In Proceedings of the fourth ACM international conference on Web search and data mining. ACM, pp. 745-754.
  * 7. Aperjis C, Huberman BA, Wu F (2010) Harvesting collective intelligence: Temporal behavior in yahoo answers.  ArXiv:1001.2320.
  * 8. Gruhl D, Guha R, Kumar R, Novak J, Tomkins A (2005) The predictive power of online chatter.  In: Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining. ACM, pp. 78-87.
  * 9. Lerman K, Tad H (2010) Using a model of social dynamics to predict popularity of news.  In: In Proceedings of the 19th international conference on World wide web. ACM, pp. 621-630.
  * 10. Barabási AL, Albert R (1999) Emergence of scaling in random networks.  Science 286: 509.
  * 11. Newman MEJ (2009) The first-mover advantage in scientific publication.  Europhysics Letters 86: 68001.
  * 12. Newman MEJ (2014) Prediction of highly cited papers.  Europhysics Letters 105: 28002.
  * 13. Medo M, Cimini C, Gualdi S (2011) Temporal effects in the growth of networks.  Physical review letters 101: 238701.
  * 14. Dezsö Z, Almaas E, Lukács A, Rácz B, Szakadát I, et al. (2006) Dynamics of information access on the web.  Physical Review E 73: 066132.
  * 15. Ratkiewicz J, Fortunato S, Flammini A, Menczer F, Vespignani A (2010) Characterizing and modeling the dynamics of online popularity.  Physical review letters 105: 158701.
  * 16. Yan Q, Wu L (2012) Impact of bursty human activity patterns on the popularity of online content.  Discrete Dynamics in Nature and Society .
  * 17. Yang J, Leskovec J (2011) Patterns of temporal variation in online media.  In: Proceedings of the fourth ACM international conference on Web search and data mining. ACM, pp. 177-186.
  * 18. Roja B, Asur S, Huberman BA (2012) The pulse of news in social media: Forecasting popularity.  In ICWSM .
  * 19. Jamali S, Rangwala H (2009) Digging digg: Comment mining, popularity prediction, and social network analysis.  In: In Web Information Systems and Mining. International Conference on. IEEE, pp. 32-38.
  * 20. Zeng A, Gualdi S, Medo M, Zhang YC (2013) Trend prediction in temporal bipartite networks: the case of movielens, netflix, and digg.  Advances in Complex Systems 16: 04n05.
  * 21. Wang D, Song C, Barabási AL (2013) Quantifying long-term scientific impact.  Science 342: 127–132.
  * 22. Zhu H, Wang X, Zhu JY (2003) Effect of aging on network structure.  Physical Review E 68: 056121.
  * 23. Facebook wall posts network dataset - KONECT.  Available: http://konect.uni-koblenz.de/networks/facebook-wosn-wall.  Accessed 20 September 2014.
  * 24. Viswanath B, Mislove A, Cha M, Gummadi KP (2009) On the Evolution of User Interaction in Facebook.  In: Proc. Workshop on Online Social Networks. pp. 37-42.
  * 25. Kunegis J (2013) KONECT - The Koblenz Network Collection.  In: Proc. Int. Web Observatory Workshop. pp. 1343-1350.
  * 26. The koblenz network collection.  Available: http://konect.uni-koblenz.de/.  Accessed 30 November 2014.
  * 27. Hanley JA, McNeil BJ (1982) The meaning and use of the area under a receiver operating characteristic (roc) curve.  Radiology 143: 29.
  * 28. Herlocker JL, Konstan JA, Terveen LG, Riedl JT (2004) Evaluating collaborative filtering recommender systems.  ACM Transactions on Information Systems (TOIS) 22: 5-53.

## Figure Legends

Figure 1:  The prediction result of TBP for Movielens, Netflix and Facebook
data sets under different $\gamma$. The performance of different $n$ values
are given. $n=50$ is presented by black lines with squares, $n=100$ is
presented by red lines with circles, and $n=200$ is presented by blue lines
with triangles.

Figure 2:  The correlation of $dr$ with $r_{k}$ for top 100 objects in the
real future. Black lines with circles present the result of TBP with the best
parameter $\gamma^{*}$, red lines with triangles present the result of PBP
with the best parameter $\lambda^{*}$, and blue lines with diamonds present
the result of TBP with $\gamma=1$. $T_{F}$ is set as 30 days for all data
sets.

Figure 3:  The performanc of TBP and PBP as a function of the future time
window $T_{F}$. TBP is presented by black lines, and PBP is presented by red
line. $n$ is set as 100. Time is measured in days.

Figure 4:  The relationship of $\gamma^{*}$ with $T_{F}$ for Movielens,
Netflix and Facebook data sets.

## Tables

Table 1:  Basic statistical features of the data sets.  Data set |  Users |  Objects |  Links |  Period
---|---|---|---|---
Movilens |  5000 |  7533 |  $8.6\times 10^{5}$ |  1st Jan 2002 - 1st Jan 2005
Netflix |  4960 |  16599 |  $1.2\times 10^{6}$ |  1st Jan 2000 - 31st Dec 2005
Facebook |  40981 |  38143 |  $8.6\times 10^{5}$ |  14th Sep 2004 - 22nd Jan 2009
Table 2: The prediction performance of temporal-based predictor (TBP) and popularity-based predictor (PBP) for Movielens, Netflix and Facebook data sets. The parameter for each predictor is set as the one corresponding to the highest $P_{n}$ value. $n$ is set as 100. Data set |  Predictor |  Parameter |  AUC |  $P_{n}$ |  $Q_{n}$
---|---|---|---|---|---
Movielens |  PBP |  0.98 |  0.988 |  0.706 |  0.432
TBP |  0.06 |  0.990 |  0.705 |  0.526
Netflix |  PBP |  0.98 |  0.960 |  0.634 |  0.502
TBP |  0.06 |  0.962 |  0.637 |  0.545
Facebook |  PBP |  0.93 |  0.893 |  0.372 |  0.217
TBP |  0.03 |  0.894 |  0.387 |  0.252