DEIM Forum 2013 A4-1

Improving revision graph extraction in Wikipedia based onsupergram decomposition
呉建民†

岩井原瑞穂‡†早稲田大学大学院情報生産システム研究科〒808-0135 福岡県北九州市若松区ひびきの ２－７
E-mail: †jianmin.wu@moegi.waseda.jp,‡iwaihara@waseda.jp

Abstract As one of the popular social media that many people turn to in recent years, collaborative encyclopedia
Wikipedia provides information in a more "Neutral Point of View" way than others. Towards this core principle, plenty ofefforts have been put into collaborative contribution and editing. The trajectories of how such collaboration appears byrevisions are valuable for group dynamics and social media research, which suggest that we should extract the underlying
derivation relationships among revisions from chronologically-sorted revision history in a precise way. With this paper, we
propose a revision graph extraction method based on supergram decomposition in the document collection of near-duplicates.
We show that this method can effectively perform the task than existing methods.
KeywordSocial Media, Web Mining, Wikipedia
research modeling Wikipedia’s revision history choose

1. Introduction
In recent years, social media becomes more and more
attractive to many people since it involves means oftrees or graphs to represent the relationship, but few ofthem concern about the accuracy of their models.

interactions among people in which they create, share,exchange and comment contents among themselves invirtual communities and networks [2]. As a collaborative
project,

onlineencyclopedia

Wikipedia

receives

contribution from all over the world [5] and its content iswell accepted by those who want reliable social news andknowledge.
Guiding by the fundamental principle of “Neutral Pointof View”, Wikipedia articles need plenty of extra editorial
efforts other than simply content expanding and fact
updating. Users can choose to edit on an existing revisionand override the current one or revert to a previous
revision. However, there is no explicit mechanism inWikipedia to trace such relationship among re visions,while the trajectories how such collaboration appears in
Wikipedia articles in terms of revisions are valuable for

Fi gu re 1. 1 Typ i cal ed it hi st ory of Wi ki p edi agroup dynamics and social media research [3]. Also,

In this research, we propose a method to model suchresearch exploiting revision history for term weighting

trajectories as revision graphs from chronologically-sorted

requires clean history without astray, which can berevision history. We derive these directed acyclic graph s

accomplished by such trajectories.

by extracting the underlying derivation relationships

Wikipedia now keeps all the versions’ contents for eachamong revisions in a precise way. For a given revision r, it

article and make the edit history publicly available. Other

needs to be compared with some previous revisions anduseful information, such as timestamps, contributors, anddecide a best candidate by some similarity measure. Basededit comments is also recorded. Figure 1.1 shows aon the characteristics of Wikipedia editing, we assume thatsnapshot of typical Wikipedia edit history. Most existing

the best candidate is the one that takes least efforts toconvert to r. More specifically:observedamong articles about non -breaking events.

a) Adding takes more efforts than deleting.

However, the similarity metric adopted in this research isb) Long edits take more efforts than short edits.

over-simplified and the correctness of the trajectories theyc) Multiple short edits take more effort than s ingle longbuild is not assured.

short edits.

Cao et al. [2] proposed a version tree reconstruction

To find candidates that meet the above requirements ismethodfor

Wikipedia

articles

based

on

keyworddifferent from nearest neighbor search (NNS) in text

clustering. This method uses tf-idf (term frequency andmining. The conventional NNS deals with text corpus that

inverted document frequency) score to cluster similar

is generally heterogeneous, while in our research the text

revisions and then largest common subsequenc es are used

content

for more precise comparison, which is closer to stringismutuallyhighly similar

in

the

revisioncollection. Common text clustering methods like kNN andmatching problem.

SimHash [11] fail to distinguish such homogeneous texts.

Wu et al. [4] proposed a revision graph extraction

There is another issue we should notice. The overview ofmethod for Wikipedia articles based on n-gram cover. This

Wikipedia mining [4] shows that the text amount of diffresearch uses n-gram distribution to denote revisions of

between two adjacent revisions is not proportional to thethe given articles with timestamps and find how alength of the article, that is, users would not contributerevision’s n-gram distribution can be formed by specificmore text because of a longer article. With the relatively

previous revisions’. But this method still suffers fromstable edit contribution amount, the longer an article

error rate due to the plain model of n -gram diff score.

grows, the less difference can be told by Jaccard distance,
which suggests that we need absolute measure.

3. Supergram Decomposition

In this paper, we first introduce existing work related to

As the further research of [4], we carefully consider theour research. In Section 3 we explain our motivation andmodel of n-gram cover. The n-gram frequency comparison

basic process of supergram decomposition. We extend themethod in n-gram cover model is from the shingling

model in Section 4 by exploiting dependencies among

method, which has been a conventional method in nearest

revisions and narrowing down comparison scope forneighbor searching [9][10]. In n-gram cover, only thescalability. Section 5 evaluates the result generated by ourdifferent text among revisions has been noted andmethod and compare with other representative methods.

measured. Diff caused by edit behaviors will be detected

Finally we conclude our paper by summarizing findings

as changes in k-gram frequency distribution. Although theand discussing several key issues.

positional information among tokens can be reserved
partially by longer shingle (bigger n), the integrity of

2. Related Workdifferent edits cannot be recovered. On the other hand, it

Basically, a revision history modeling method should
include three components: text differencing method,

takes too much time to achieve integrity by longest
common subsequence based diff algorithm.

similarity measurement and comparison strategy. Most

We find that there are some token sequences that keep

existing work focused on the first component. P. Fong et al

as a unit throughout the whole revision collection. For a[3] proposed a detail text differencing algorithm that finds

small revision collection of several revisions, such token

all the different parts, including the case of phrase

sequences is little but with long length. As the size of the

movement and sentence re-writing, between two given

revision collection grows larger, long token sequences arerevisions based on hierarchical decomposition and thesplit into shorter fragile due to modifications. Formally,

longest common string method,

we define such units as:

which is however way

too computationally expensive in terms of large scale
revision comparison.
In an investigation on structure and dynamics of
Wikipedia’s breaking news collaborations [3], Keegan etal. construct article trajectories of editor interactions as
they coauthor an article. Examining a subset of this corpus,
their analysis demonstrates that articles about cur rent
events exhibit structures and dynamics distinct from those

DEFINITION 3.1. Supergram
A supergram s=t 1 t 2 ..t n in a revision collection R is an
n-gram (n>=2) such that s occurs in at least one revision in
R, and if a token t i (1<i<n) occurs in a revision R’, thent i+ 1 always occurs just after t i in R’.
Basically, for the revision collection R of an article, we
extract the supergrams by path contraction on wordtransition graph, and utilize supergram diff to compare

revisions. More concretely, our method consists of thev i : vertex i labeled with t i ;following steps:

e x (v i , v j ): edge x from v i to v j , labeled with the

1. Pre-processing.

Aftertext-cleansing

andcollection frequency of bigram t i t j ;URLreplacement, split all revisions into bigrams and

out(v i ): set of all edges from v i ;construct a global inverted index I of bigrams onin(v i ): set of all edges to v i ;revisions.

src(e): source vertex of edge e;tar(e): target vertex of edge e

2. Word transition graph construction. By scanningeach revision, construct a word transition graph G for
the revision collection. Compact G into a weighted
multigraph G' by path contraction, extract the edges’
weights in G' to construct the supergram list S.
3. Supergram decomposition. Decompose each revision
based on S, then construct an inverted index of S on
revisions.

Regarding

all

terms

appearinginS,

construct an inverted index of terms on S.
Pre-processing

Unigram token sequence
Word transition
graph construction& path contraction

DEFINITION 3.2 Word transition graph
Given a document r on vocabulary D, a word transition
graph G=(V, E) is a directed weighted graph such thateach vertex v i

V denotes a term t i

D. For two terms t

and t j D, a weighted directed edge e(v i , v j )E exists

between their corresponding vertices v i , and v j if and only
if the bigram t i t j has a frequency f(t i t j ) > 0 in R, and f(t i t j )is assigned as the edge weight.
The word transition graph is allowed to contain cycles
since the multiple appearance of frequent terms causes
path that starts and ends at the same vertex but otherwise
has no repeated vertices or edges. On the other hand, there
exist chain-like subgraphs at which only one path exists ,which correspond to Definition 3.1. Here we define such
structure formally:
DEFINITION 3.3 Chain

Supergram set

A chain C=(V’, E’) is a subgraph of G containing only
one connected component, with the property that every

Supergramdecomposition
Figure 3.1 Process of s upergram decomposition .

vertex v’ i V’ , except the two ends, has only one
incoming edge and one outgoing edge, i.e. |out(v’ i )| =|in(v’ i )| = 1, and v’ iis called a chain vertex. The

starting vertex of C, namely the source, is defined as thevertex v s such that |out(v s )| = 1 and |in(v s )|3.1 Pre-processing

1. The sinkis defined similarly.

We first split the original revision text into a unigram
token sequence. The text content in the original revision

Path contraction

files contains plenty of Wiki Markups, which give specificBy path contraction, each edge e' (v i , v j ) should satisfy

semantic tags on plain text. While splitting the text, such

both:

markups are extracted by regular expression and will bea) Correctness.

reserved as single tokens in the following steps. The

For any bigram titj in revision collection R, its

second task is replacing the URLs appearing in the text.

frequency f(titj) is equal to the supergram frequency f(sk)No matter how many terms a URL involves, it has no morein R, where sk is the supergram that contains titj.

contribution to add a new URL than to add a single word.
We replace each URL with a 16-byte string generated by
MD5 for consistency.

b) Compactness.
If the source of e' has no in-degree ( |in(src(e'))| = 0),
the target of e' should have more than 1 out-degree

3.2 Word transition graph construction(|out(tar(e'))| > 1). Otherwise the total degree of source

Given an article R with versions r 1 , r 2 , …, r n , each of themand target should be more than 3.

contains a sequence of tokens D i = [t 1 , t 2 , …, t l ]. In thefollowing paragraphs, we denote

Regarding such requirements, we describe the algorithm
as follows:Algorithm for path contraction:

For each revision r i , calculate r i ’s comparison scope

Input: G = (V, E)
For each vertex v ifor each v j

1. Comparison scope determination

V, If |out(v i )| > 0,out(v i ),If v j is a chain vertex with an outgoing edge e(v j ,v k ), create a new edge e’(v i , v k ) and label it with theconcatenation of the label of e(v i , v j ) and v k ’s
corresponding term t k , and delete v j from G.
Notice that each revision can be treated as a token
sequence starting from the same source “$” and sinking
with the same terminator “^”, there is no need to consider
the cases of |out(v i )| = 0, or |in(v i )| = 0.
After path contraction, the original word transition
graph is contracted to a multigraph such that each vertex
v' i 's corresponding term t i has a frequency f(t) > 0 in at

C i based on r i ’s timestamps and global bigram inverted
index I.
2. Sliding decomposition
Construct a word transition graph G i of all therevisions within C i , and perform path contraction for G i to
get G i ’. Decomposed r i ’ and all revisions in C i into
supergram frequency distribution based on the supergram
set S extracted from G i ’.
3. Supergram diff score computing.
Compare r i ’s supergram frequency distribution withall revisions’ in C i and compute their supergram diffscores.

least one revision, and each edge e(t i , t j ) representing a

4. Candidate selection.

supergram s in either ways:

Pick up the revisions with lowest k supergram diff scorea) If the edge label is a concatenation of (freq|terms), s
is a new concatenation of t i + terms +t j .

as the candidates for parents.
Pre-processing

Timestampsb) If the edge label is an integer, s = t i t j
3.3 Supergram decomposition

Unigram token

Decompose each revision based on supergram set S,

Scope computing

sequence

construct an inverted index of S on revisions. Regarding
all terms appearing in S, construct an inverted index of

Sliding Word

terms on S. Then all revisions’ supergram frequency

transition graphdistribution can be compared based on S.

construction

Supergram set

4. Comparison
Recall the observation of supergram we mentioned
before: a narrower scope will produce longer supergrams .
This is because the number of edits is proportional to theSupergramdecomposition

scope length and fewer edit mean smaller chances, andFigure 3.2 Slidi ng dec ompos iti on.

supergrams tend to be undivided. Longer supergram ispreferable in supergram decomposition because it reserve

The above figure shows the basic process ofmore integrity and reduce the total number of supergrams.

decomposition based on sliding word transition graph. We

Another strong reason for scoping is scalability. In

describe major components in detail in the following

Wikipedia, articles pose various numbers of revisions

sections.

from tens to tens of thousands. Without any heuristics, ittakes O(N 2 ) time to perform full pairwise comparison for
an article posing N revisions, which is a unbearable
expense of computing resource especially for those
popular articles with thousands of revisions. Regardingthese issues, we extend the global decomposition byintroducing a sliding comparison scope and finish thewhole comparison on revision collection. The comparison
stage consists of 4 parts:

4.1 Comparison scope decision
In a near-duplicate collection without any auxiliary
information, it is hard to apply aggregation technique todivide the collection into several non-overlapping subsets.
Fortunately, Wikipedia edit history is naturally sequential.
We can draw the assumption based on the characteristics
of Wikipedia editing: The further one revision is from thecurrent revision, the less possible that the current one isderived from that revision.

perspective.
Another issue we should notice is the p henomenon of
remote copy, which is the behavior that copying a piece oftext from an ancient revision such that there is noappearance of such text within the scope of Maximum
comparison scope. Simply expanding the scope to thatancient

revisionincludesunnecessary

revisionsandlowers the efficiency. We choose to include this kind ofancient revision as individual revision alone. Formally, an
Fi gu re 4. 1 Ed it cou n t of Wi ki p ed i a art i cle " B arack O b ama" d u ri n g 2008, t h eyear of t h e U. S. p resi d en t i al elect i on 1.

But before we limit the comparison scope to a fixed
number of previous revisions, we consider the frequentancient revision is identified as follows :A revision r j is a potential remote ancestor of r i if andonly if there is a bigram b k that appears in rj and ri but not
in revisions between rj and ri.

edit behavior within a certain period of time as anotherimportant factor according to the timestamps in th e edit
history's meta information. Intense editing activity could
be caused b y edit wars, increasing popularity of the article,
or immediate updates after related events happen, and thetotal number of edits in a week could easily exceed any
preset number. Figure 4.1 shows the edit count of

4.2 Supergram diff score computing
For pairwise revision comparison, we first create thesupergram diff for two revisions, and then calculate thesupergram diff score to measure their difference.
DEFINITION 4.2. Supergram diff
Given a supergram set S, we denote the supergram

Wikipedia article "Barack Obama" during 2 008, the year

frequency distribution of revision r a as f(s i , r a ) ( s iof the U.S. presidential election, and significant peak can

For two revisions r a and r b , the supergram diff SD is thebe found in November, when the election was held. Thus,

set of supergrams with a non -zero residual frequency

all the previous revisions within certain time span should

between r a and r b :S).

be examined, regarding the fact that contributors' attention(4.1)

can last for a period of time.
Fixed scope would not be able to capture the whole

DEFINITION 4.3. Supergram diff scoreprocess of the intense edit activity, while fixed time spancan cover only little revisions. Considering such trade -off,diffScore( ,)=+we employ maximum comparison scope to denote the(4.2)

biggest number of previous revisions to be compared,
which is defined as below.

where SD a d d is the set of all supergrams such that

DEFINITION 4.1 Maximum comparison scope:, and SD del is defined similarly, w i is

Given a revision history H = {(r 1 , t 1 ) , (r 2 , t 2 ), ..., (r m ,the weight for discrimination between adding and deletingt m )} ,where (r i , t i ) denote a revision r i with its timestamp t i ,operations. As heuristics, the logarithms are to the base of

the maximum comparison scope C for revision r k is

10, since the deleting operations is less effort -taking job.

determined by either:
4.3 Candidate selectiona). If t k - t k-T > T, C = S l orb).if

p > 0 such that t k - t k-p

T and t k - t k- p- 1 > T, C =It is possible that with the lowest supergram diff scorepthere come multiple revisions with the same score. For

where S l denotes the least scope to ensure enoughexample, if a revision r just revert to one previous revisioncomparison for unpopular documents, T denotes the leastr ’, the child of r has at least 2 revisions that have the sametime span for intense edits.

supergram diff score. To avoid ambiguity, we define that

Notice that there could be a series of consecutive edits
by the same contributor, we take the latest revision only
and omit the others, since we focus on the collaborative
authoring and editing process rather than individual1

http://en.wikipedia.org/wiki/Barack_Obama

the parent revision should be the one with the latest
timestamp in such cases.

5. Experimental evaluation

where

are the transitive closures of G 1 ,G 2 ,We conduct experimental evaluation on our method

is half the number of all the node pairs . By formula (5.1)

against several existing revision relationship modeling

we focus on how far(in terms of number of total descant

methods on a collection of Wikipedia articles.

revisions) an error can reach , so errors that happen in theearly stage or those that involve more

Article
#
1
2
3
4
5
6
7
8
9
10

Article Title

revisions have greater loss in accuracy.

#ofBranches
23
12
37
16
33
15
24
11
8
12

Racism2006 Israel–Gaza conflict
PhpBB
Edith Wharton
Federal republic
Sarkar Raj
Grade inflation
Natal chart
Muhammad Naguib
Clarinet Concerto

succeeding

100%
90%
80%
Supergram

70%

NgramCover60%

Keyword50%

Jaccard

40%
30%
20%
0

2

4

6

8

10

12

Table 5.1 Ground Truth Sta ti stics

To evaluate the performance of the proposed method, w e
conductaseriesofaccuracy

evaluation

with

Figure 5.1 Reachability accuracy

3

representative methods: sentence-level Jaccard distance,

6. Conclusion

keyword clustering, n-gram cover. For each method, we

In this paper, we proposed supergram technique forcomparemanuallyaccurate reconstruction of Wikipeida revision history.

constructed graphs on the existing ground truth [4] . As

Supergrams are extracted from a wo rd transition graph byshown in Table 5.1, the data set contains 10 Wikipedia

path

articles totaling 2000 revisions. The branch counts

previous approach by the n -gram cover.

its

resultrevision

graph

with

contraction.

Our

proposedmethod outperforms

indicate the total revert events and diversity, potentiallysuggesting the degree of popularity and controversy. All
the revisions have been pre-processed according toReferences

Section 3.1 so that all methods start with the same token[1] Wilkinson, D. M. and Huberman, B. A. Cooperationand quality in wikipedia. In Proc. WikiSym'07(Montreal, Quebec, Canada 2007). ACM.
[2] Ahlqvist, Toni; Bäck, A., Halonen, M., Heinonen, S.
"Social media roadmaps exploring the futures
triggered by social media". VTT Tiedotteita - Valtion
Teknillinen Tutkimuskeskus (2454): 13.,2008[3] Brian Keegan, Darren Gergle, Noshir Contractor,
Staying in the Loop: Structure and Dynamics of
Wikipedia's Breaking News Collaborations in Proc.
WikiSym'12. ACM.
[4] Jianmin Wu, Mizuho Iwaihara, "Wikipedia revisiongraph extraction based on n -gram cover", Proc. Int.
Workshop on Graph Data Management and Mining,
WAIM 2012 , Lecture Note in Computer Science
7419, pp. 29–38, 2012
[5] A. Lih. Wikipedia as participatory journalism:
Reliablesources:
Metricsforevaluating
collaborative media as a news resource. Proc. Int.
Symp. Online Journalism 2004
[6] Myers, E, An O(ND) Difference Algorithm and Its
Variations. Algorithmica, 1(2): 251–266 , 1986
[7] Sabel, M.. Structuring wiki revision history.
WikiSym pp. 125-130, 2007
[8] U. Manber, "Finding similar files in a large filesystem," Proc. USENIX Conference, pp. 1 -10, 1994.

sequence.
The parent accuracy is evaluated by the percentage ofthe revisions that has the correct parent.
100%
90%
80%

Supergram
NgramCover

70%

Keyword60%

Jaccard

50%
40%
0

2

4

6

8

10

12

Figure 5.1 Parent accuracy

We evaluate branching errors that happen in different
stages by reachability comparison. Given two revisiongraphs G 1, G 2 on the same revision collection D, thereachability accuracy of G 2 on G 1 is defined as follows:(5.1)

[9] A.Z. Broder, "On the resemblance and containment of
documents," Proc. Compression and Complexity ofSequences, pp. 21-29, Positano Italy, 1997.
[10] Cao, Z., Iwaihara, M., Wikipedia version tree
reconstruction by clustering revisions throughkeywords, IEICE Technical Report DE2011 -32, 2011[11] Gurmeet Singh Manku, Arvind Jain, and Anish Das
Sarma. Detecting near-duplicates for web crawling.
In Proceedings of the 16th international conference
on WWW '07. ACM, New York, NY, USA,2007