text: uses a weak classiﬁer at each split node to route an item to the graph elements unpredictably has an averse affect on utility. Hence, “left” or “right” child node based on its features. The item is routed the very fact node degrees are predictably perturbed also allows us down the tree, ultimately reaching a leaf node where one class, or to mount an attack: we expect the distribution of degrees in the a distribution over classes, is assigned. The features on which the neighborhood of sub-graph nodes to be related between different split node predicates are deﬁned is problem speciﬁc – we propose ego-nets. Furthermore, neighborhood degree distribution can be features to represent an anonymized graph in Section . efﬁciently computed. Training and testing. The tree training phase involves injecting For each node in the social s∈ociZal network we deﬁne a feature labeled data into the tree to optimize the split parameters at the vector v = (c0, c1, . . . , cn−1) of length n made up of com- internal nodes and determining the leaf predictors. Each internal ponents which are bins of size b. Each component represents the node of the tree is associated with a binary classiﬁer also known number of neighbors that have a degree in a particular range. The apcshariwladmeoaefktetlrhe.earHsnpeelrirte,nwSohLdoed,seeSnoRouttdepseunttohdteeessceitdhteeosfstephtoeoinfdtapstoapinastspssleiptdafsotsoredathtgeoivlteehfnet igIftrhetheceosdmuecpghoretnheeanettxicis·eebthd<es tchdoeeugmnrteacexii≤mofu(mtih+epon1su)smi·bbblee,rwraohnfegnreeeioigfh∈nbo·{rb0s,twhneint−hitd1ie}s-. right child. We denote S as the set SL ∪ SR of all items used to included in the last bin. train a split node. To train each split node we select the feature that Binning of neighborhood degrees is performed for efﬁciency and maximizes the information gain objective function: performance. Since the exact degree of the nodes across different (cid:88) anonymized sub-graphs may vary, the exact degree is irrelevant, | S | and binning increases matching robustness. In our experiments we I = H(S) − | Si| H(Si) (1) use n = 70 and b = 15. Figure 3 illustrates the feature vector i∈{L,R} v{ = (8, 4, 0, 0, 3, 0, . . . , 0, 2) of a node with neighbors of de}grees – 1, 1, 3, 3, 5, 6, 7, 13, 16, 20, 21, 30, 65, 69, 72, 1030, 1100 . S S where H( ) is the Shannon entropy of the labels in set with C elements belonging to the set of classes . Maximizing the informa- n=70bins ... ... tion gain at every split node decreases entropy of data and increases conﬁdence in tree prediction. Each leaf node stores the empirical c0 = 8 c1 = 4 c2 = 0 ... c4 = 3 ... c69 = 2 distribution of the classes associated with the subset of training data sizeb=15 reaching that leaf node. The predictor is deﬁned as the probability Figure 3: Example node feature vector of a data point belonging to a particular class based on the distri- bution. We only use binary classiﬁcation, hence we have just two Apart from the depicted values all bins contain 0’s. classes. 3.4 Training and Classiﬁcation of Node Pairs The decision forest model. The trees of a random forest are trained independently in parallel. A data point is classiﬁed by pushing it The basic data point to be classiﬁed consists of a pair of node through all the trees, branching left or right within each tree accord- features, each in a different egonet sub-graph. Let us denote the ing to the item features, until it reaches the leaves of all trees (this feature vector belonging to a node n to be v . Each node pair p p process can also be parallelized). The prediction of each tree at the (n , n ) is represented as a pair of vectors (v , v ). The node pair p q p q corresponding leaf node is averaged to generate an aggregate forest can be labeled as either “identical”, if the nodes n and n are the p q prediction, deﬁned as same nodes in different egonets; or “non-identical” if n and n are (cid:88) p q in fact different nodes. The objective of the classiﬁcation task is to infer the label of the pair (n , n ) on the basis of the feature vectors p(c|v) = T1 t=T1 pt(c|v) (2) Tvpraainndinvgq.& Weak Learnerp. Weq use both bagging [3] and random- | ized node optimization [10] to train decision trees. The trees are where p(c v) is the empirical probability (as computed by the trained by injecting a random sample of data points at the root node. random forest) that given a feature vector v, it|belongs to a data point The sample contains data points of each class in equal proportion. of class c, T is the number of trees and pt(c v) is the prediction of The weak learner at each split node is presented with pairs of an individual tree. We use T = 400 trees in our experiments. feature vectors (v , v ) and needs to decide whether they are as- p q 3.3 Specialized Social Graph Features signed to the left or the right child node. To decide the split our weak learner uses the Silhouette Coefﬁcient between two sample Random forests rely on ﬁnding features that when combined us- features x ∈ v and y ∈v deﬁned as: ing many weak learners, classify the data accurately. Training en- p q sures that the best features are retained, and their best conjunction will be selected per tree. Different trees allow disjunctions of fea- 0 if x = y = 0 | − | tures to contribute to classiﬁcation. δ(x, y) = x y (3) otherwise A balance must be struck between too generic or too speciﬁc fea- max(x, y) tures. If the features are too generic, in that they appear in most ∈ Z sub-graphs, then classiﬁcation will be akin to guessing. On the where x, y . Thus, for each feature pair (v , v ) we can p q ∈ other hand if they are too speciﬁc and rely on intricate graph struc- calculate all n2 component pairs δ(v [i], v [j]), where i, j { − } p q tures, then they may be seriously damaged during anonymization. 0, n 1 . For a given component pair (v [i], v [j]) the tree com- p q In all cases efﬁcient feature extraction is important to allow for fast putes δ(v [i], v [j]) and passes the data point to the left or the right p q training and evaluation. child depending upon threshold τ. During training each split node We use the degrees (number of friends) of the “friends" of a node is assigned a τ that splits the data for a given (v [i], v [j]) to maxi- p q as features. Most anonymization strategies strive to preserve some mize information gain. To choose the best τ for a given (v [i], v [j]) ∈ p q utility of the data, and damaging such a fundamental property of we cycle through τ [0, 1] in steps of 0.05. We inject randomness ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: uses

text: a

text: weak

text: classiﬁer

text: at

text: each

text: split

text: node

text: to

text: route

text: an

text: item

text: to

text: the

text: graph

text: elements

text: unpredictably

text: has

text: an

text: averse

text: affect

text: on

text: utility.

text: Hence,

text: “left”

text: or

text: “right”

text: child

text: node

text: based

text: on

text: its

text: features.

text: The

text: item

text: is

text: routed

text: the

text: very

text: fact

text: node

text: degrees

text: are

text: predictably

text: perturbed

text: also

text: allows

text: us

text: down

text: the

text: tree,

text: ultimately

text: reaching

text: a

text: leaf

text: node

text: where

text: one

text: class,

text: or

text: to

text: mount

text: an

text: attack:

text: we

text: expect

text: the

text: distribution

text: of

text: degrees

text: in

text: the

text: a

text: distribution

text: over

text: classes,

text: is

text: assigned.

text: The

text: features

text: on

text: which

text: the

text: neighborhood

text: of

text: sub-graph

text: nodes

text: to

text: be

text: related

text: between

text: different

text: split

text: node

text: predicates

text: are

text: deﬁned

text: is

text: problem

text: speciﬁc

text: we

text: propose

text: ego-nets.

text: Furthermore,

text: neighborhood

text: degree

text: distribution

text: can

text: be

text: features

text: to

text: represent

text: an

text: anonymized

text: graph

text: in

text: Section

text: efﬁciently

text: computed.

text: Training

text: and

text: testing.

text: The

text: tree

text: training

text: phase

text: involves

text: injecting

text: For

text: each

text: node

text: in

text: the

text: social

text: s∈ociZal

text: network

text: we

text: deﬁne

text: a

text: feature

text: labeled

text: data

text: into

text: the

text: tree

text: to

text: optimize

text: the

text: split

text: parameters

text: at

text: the

text: vector

text: v

text: of

text: length

text: n

text: made

text: up

text: of

text: com-

text: internal

text: nodes

text: and

text: determining

text: the

text: leaf

text: predictors.

text: Each

text: internal

text: ponents

text: which

text: are

text: bins

text: of

text: size

text: b.

text: Each

text: component

text: represents

text: the

text: node

text: of

text: the

text: tree

text: is

text: associated

text: with

text: a

text: binary

text: classiﬁer

text: also

text: known

text: number

text: of

text: neighbors

text: that

text: have

text: a

text: degree

text: in

text: a

text: particular

text: range.

text: The

text: right

text: child.

text: We

text: denote

text: S

text: as

text: the

text: set

text: SL

text: SR

text: of

text: all

text: items

text: used

text: to

text: included

text: in

text: the

text: last

text: bin.

text: train

text: a

text: split

text: node.

text: To

text: train

text: each

text: split

text: node

text: we

text: select

text: the

text: feature

text: that

text: Binning

text: of

text: neighborhood

text: degrees

text: is

text: performed

text: for

text: efﬁciency

text: and

text: maximizes

text: the

text: information

text: gain

text: objective

text: function:

text: performance.

text: Since

text: the

text: exact

text: degree

text: of

text: the

text: nodes

text: across

text: different

text: anonymized

text: sub-graphs

text: may

text: vary,

text: the

text: exact

text: degree

text: is

text: irrelevant,

text: S

text: and

text: binning

text: increases

text: matching

text: robustness.

text: In

text: our

text: experiments

text: we

text: I

text: H(S)

text: Si|

text: H(Si)

text: use

text: n

text: and

text: b

text: Figure

text: illustrates

text: the

text: feature

text: vector

text: i∈{L,R}

text: v{

text: of

text: a

text: node

text: with

text: neighbors

text: of

text: de}grees

text: S

text: S

text: where

text: H(

text: is

text: the

text: Shannon

text: entropy

text: of

text: the

text: labels

text: in

text: set

text: with

text: C

text: elements

text: belonging

text: to

text: the

text: set

text: of

text: classes

text: Maximizing

text: the

text: informa-

text: tion

text: gain

text: at

text: every

text: split

text: node

text: decreases

text: entropy

text: of

text: data

text: and

text: increases

text: conﬁdence

text: in

text: tree

text: prediction.

text: Each

text: leaf

text: node

text: stores

text: the

text: empirical

text: distribution

text: of

text: the

text: classes

text: associated

text: with

text: the

text: subset

text: of

text: training

text: data

text: reaching

text: that

text: leaf

text: node.

text: The

text: predictor

text: is

text: deﬁned

text: as

text: the

text: probability

text: Figure

text: Example

text: node

text: feature

text: vector

text: of

text: a

text: data

text: point

text: belonging

text: to

text: a

text: particular

text: class

text: based

text: on

text: the

text: distri-

text: bution.

text: We

text: only

text: use

text: binary

text: classiﬁcation,

text: hence

text: we

text: have

text: just

text: two

text: Apart

text: from

text: the

text: depicted

text: values

text: all

text: bins

text: contain

text: classes.

text: Training

text: and

text: Classiﬁcation

text: of

text: Node

text: Pairs

text: The

text: decision

text: forest

text: model.

text: The

text: trees

text: of

text: a

text: random

text: forest

text: are

text: trained

text: independently

text: in

text: parallel.

text: A

text: data

text: point

text: is

text: classiﬁed

text: by

text: pushing

text: it

text: The

text: basic

text: data

text: point

text: to

text: be

text: classiﬁed

text: consists

text: of

text: a

text: pair

text: of

text: node

text: through

text: all

text: the

text: trees,

text: branching

text: left

text: or

text: right

text: within

text: each

text: tree

text: accord-

text: features,

text: each

text: in

text: a

text: different

text: egonet

text: sub-graph.

text: Let

text: us

text: denote

text: the

text: ing

text: to

text: the

text: item

text: features,

text: until

text: it

text: reaches

text: the

text: leaves

text: of

text: all

text: trees

text: (this

text: feature

text: vector

text: belonging

text: to

text: a

text: node

text: n

text: to

text: be

text: v

text: Each

text: node

text: pair

text: p

text: p

text: process

text: can

text: also

text: be

text: parallelized).

text: The

text: prediction

text: of

text: each

text: tree

text: at

text: the

text: (n

text: n

text: is

text: represented

text: as

text: a

text: pair

text: of

text: vectors

text: (v

text: v

text: The

text: node

text: pair

text: p

text: q

text: p

text: q

text: corresponding

text: leaf

text: node

text: is

text: averaged

text: to

text: generate

text: an

text: aggregate

text: forest

text: can

text: be

text: labeled

text: as

text: either

text: “identical”,

text: if

text: the

text: nodes

text: n

text: and

text: n

text: are

text: the

text: p

text: q

text: prediction,

text: deﬁned

text: as

text: same

text: nodes

text: in

text: different

text: egonets;

text: or

text: “non-identical”

text: if

text: n

text: and

text: n

text: are

text: p

text: q

text: in

text: fact

text: different

text: nodes.

text: The

text: objective

text: of

text: the

text: classiﬁcation

text: task

text: is

text: to

text: infer

text: the

text: label

text: of

text: the

text: pair

text: (n

text: n

text: on

text: the

text: basis

text: of

text: the

text: feature

text: vectors

text: p(c|v)

text: pt(c|v)

text: Tvpraainndinvgq.&

text: Weak

text: Learnerp.

text: Weq

text: use

text: both

text: bagging

text: and

text: random-

text: ized

text: node

text: optimization

text: to

text: train

text: decision

text: trees.

text: The

text: trees

text: are

text: where

text: p(c

text: v)

text: is

text: the

text: empirical

text: probability

text: (as

text: computed

text: by

text: the

text: trained

text: by

text: injecting

text: a

text: random

text: sample

text: of

text: data

text: points

text: at

text: the

text: root

text: node.

text: random

text: forest)

text: that

text: given

text: a

text: feature

text: vector

text: v,

text: it|belongs

text: to

text: a

text: data

text: point

text: The

text: sample

text: contains

text: data

text: points

text: of

text: each

text: class

text: in

text: equal

text: proportion.

text: of

text: class

text: c,

text: T

text: is

text: the

text: number

text: of

text: trees

text: and

text: pt(c

text: v)

text: is

text: the

text: prediction

text: of

text: The

text: weak

text: learner

text: at

text: each

text: split

text: node

text: is

text: presented

text: with

text: pairs

text: of

text: an

text: individual

text: tree.

text: We

text: use

text: T

text: trees

text: in

text: our

text: experiments.

text: feature

text: vectors

text: (v

text: v

text: and

text: needs

text: to

text: decide

text: whether

text: they

text: are

text: as-

text: p

text: q

text: Specialized

text: Social

text: Graph

text: Features

text: signed

text: to

text: the

text: left

text: or

text: the

text: right

text: child

text: node.

text: To

text: decide

text: the

text: split

text: our

text: weak

text: learner

text: uses

text: the

text: Silhouette

text: Coefﬁcient

text: between

text: two

text: sample

text: Random

text: forests

text: rely

text: on

text: ﬁnding

text: features

text: that

text: when

text: combined

text: us-

text: features

text: x

text: v

text: and

text: y

text: ∈v

text: deﬁned

text: as:

text: ing

text: many

text: weak

text: learners,

text: classify

text: the

text: data

text: accurately.

text: Training

text: en-

text: p

text: q

text: sures

text: that

text: the

text: best

text: features

text: are

text: retained,

text: and

text: their

text: best

text: conjunction

text: will

text: be

text: selected

text: per

text: tree.

text: Different

text: trees

text: allow

text: disjunctions

text: of

text: fea-

text: 0

text: if

text: x

text: y

text: tures

text: to

text: contribute

text: to

text: classiﬁcation.

text: δ(x,

text: y)

text: x

text: y

text: otherwise

text: A

text: balance

text: must

text: be

text: struck

text: between

text: too

text: generic

text: or

text: too

text: speciﬁc

text: fea-

text: max(x,

text: y)

text: tures.

text: If

text: the

text: features

text: are

text: too

text: generic,

text: in

text: that

text: they

text: appear

text: in

text: most

text: Z

text: sub-graphs,

text: then

text: classiﬁcation

text: will

text: be

text: akin

text: to

text: guessing.

text: On

text: the

text: where

text: x,

text: y

text: Thus,

text: for

text: each

text: feature

text: pair

text: (v

text: v

text: we

text: can

text: p

text: q

text: other

text: hand

text: if

text: they

text: are

text: too

text: speciﬁc

text: and

text: rely

text: on

text: intricate

text: graph

text: struc-

text: calculate

text: all

text: component

text: pairs

text: δ(v

text: [i],

text: v

text: [j]),

text: where

text: i,

text: j

text: p

text: q

text: tures,

text: then

text: they

text: may

text: be

text: seriously

text: damaged

text: during

text: anonymization.

text: n

text: For

text: a

text: given

text: component

text: pair

text: (v

text: [i],

text: v

text: [j])

text: the

text: tree

text: com-

text: p

text: q

text: In

text: all

text: cases

text: efﬁcient

text: feature

text: extraction

text: is

text: important

text: to

text: allow

text: for

text: fast

text: putes

text: δ(v

text: [i],

text: v

text: [j])

text: and

text: passes

text: the

text: data

text: point

text: to

text: the

text: left

text: or

text: the

text: right

text: p

text: q

text: training

text: and

text: evaluation.

text: child

text: depending

text: upon

text: threshold

text: τ.

text: During

text: training

text: each

text: split

text: node

text: We

text: use

text: the

text: degrees

text: (number

text: of

text: friends)

text: of

text: the

text: “friends"

text: of

text: a

text: node

text: is

text: assigned

text: a

text: τ

text: that

text: splits

text: the

text: data

text: for

text: a

text: given

text: (v

text: [i],

text: v

text: [j])

text: to

text: maxi-

text: p

text: q

text: as

text: features.

text: Most

text: anonymization

text: strategies

text: strive

text: to

text: preserve

text: some

text: mize

text: information

text: gain.

text: To

text: choose

text: the

text: best

text: τ

text: for

text: a

text: given

text: (v

text: [i],

text: v

text: [j])

text: p

text: q

text: utility

text: of

text: the

text: data,

text: and

text: damaging

text: such

text: a

text: fundamental

text: property

text: of

text: we

text: cycle

text: through

text: τ

text: in

text: steps

text: of

text: We

text: inject

text: randomness

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: cannot be generalized to other cases or schemes. Table 2: Epinions (self-validation): False Positive vs. True Positive for both schemes Table 1: Success percentage for ad-hoc de-anonymization of Scheme 1 for Case 1 node pairs Scheme 1 False Positive 0.01% 0.1% 1% 10% 25% Success percentage 1-hop 70.81 90.39 96.80 99.38 99.63 Identical Non-identical 1,2-hop 30.35 46.82 67.25 87.15 93.35 Epinions 100 99.98 2-hop 5.11 17.36 35.32 68.42 84.65 Pokec 100 99.96 Complete 4.41 17.76 35.67 68.08 83.79 Scheme 2 False Positive 0.01% 0.1% 1% 10% 25% The automatic machine learning approach can be generalized to all cases of both schemes, as summarized in Table 2. For the sake of 1-hop 35.08 52.92 82.87 97.33 100.00 direct comparison, for Scheme 1 using a ﬁxed small false positive 1,2-hop 11.37 25.95 62.11 83.95 93.70 rate (0.1%) we can recover 90.39% of Case 1 links; we also recover 2-hop 1.86 7.33 47.71 99.98 100.00 46.82% of Case 2 links, and 17.36% of Case 3 links. The attack Complete 0.34 5.89 36.33 94.99 98.62 generalizes to Scheme 2 where we can recover 52.92%, 25.95% and 7.33% of links in Cases 1, 2 and 3 respectively. Despite Scheme 2 leading to lower re-identiﬁcation rates, for a ﬁxed false positive rate, Table 3: Pokec (self-validation): False Positive vs. True Positive for we observe they are never negligible, and a released dataset is likely both schemes to lead to the linkage of a signiﬁcant number of individuals between “unlikable” sub-graphs. For even smaller false positives a signiﬁcant number of Case 1 links are recoverable: 70.81% for Scheme 1 and Scheme 1 35.08% for Scheme 2. Case 2 linkage is also never negligible and False Positive 0.01% 0.1% 1% 10% 25% higher than 11.37% for both Schemes. If the adversary has any side information (such as seed nodes) that can be used to establish 1-hop 27.50 42.92 51.04 88.75 93.96 a good prior, a higher rate of false positives (1%) can be tolerated 1,2-hop 5.25 11.58 36.16 73.24 88.68 with linkage rates of over 35.67% even for the hardest Case 3 links. 2-hop 0.00 12.55 23.15 49.14 69.96 Figure 6 (Appendix ) illustrates the ROC curves for Scheme 1 and Complete 0.01 10.44 20.48 47.60 68.36 Scheme 2 for all types of node pairs along with area under the ROC Scheme 2 curve (AUC). We note that the AUC for Scheme 2 is consistently above 95% for all link categories, higher than for Scheme 1 for False Positive 0.01% 0.1% 1% 10% 25% Cases 2 and 3. This is due to the classiﬁer performing signiﬁcantly 1-hop 4.20 16.26 49.89 97.20 99.58 better for Scheme 2 when high false positive rates can be tolerated 1,2-hop 0.79 6.41 28.32 73.88 94.66 – which may or may not be the case depending on adversary side 2-hop 1.62 12.12 50.42 99.96 99.99 information. Complete 0.68 6.12 21.14 64.12 86.10 Overall, the machine learning approach yields good results for Scheme 1, Cases 2 and 3 which the ad-hoc de-anonymization could not attack. More importantly, it yields good results for Scheme 2, on which the ad-hoc attack was not applicable. As expected, we get Pokec (Table 5), and vice versa, we use the classiﬁer trained on better results for the 1-hop category of node pairs, and for Scheme 1, 1000 Pokec ego-nets to classify the Epinions test data (Table 4). which retain the most information from the original graph. Pokec. The results on the Pokec network are summarized in Table 3, The two networks are of a totally different nature: Epinions is a small web-of-trust on a consumer reviews site; Pokec is a much and are similar to Epinions, which supports the general applicabil- larger national social network. ity of the attack. The ad-hoc attack against Scheme 1 gives almost perfect results. For Case 1 and 2 links the true positive linkage rate It is clear that a different training distribution has a detrimental ef- of the machine learning re-identiﬁcation procedure is 42.92% and fect on the quality of classiﬁcation for very low false positive values. 11.58% for Scheme 1; for Scheme 2 they are 16.26% and 6.41% re- For a false positive rate of 0.1% Case 1, 2 and 3 links in the Pokec spectively (for a 0.1% false positive rate). Interestingly, the linkage network are linked at a rate of 27.29%, 10.10% and 4.18% respec- rate for Case 3, which was the lowest in the Epinions network, now tively for Scheme 1, and 5.40%, 2.08% and 13.57% for Scheme 2 outperforms Case 2 and is on par with Case 1 when higher false (Table 5). The results on the Epinions network see a similar fall positive rates are tolerable. This is likely due to a lower degree of (Table 4). Despite this, they never become small enough to guar- overlap in the neighborhood of non-identical nodes resulting from antee that the likelihood of linking is negligible. For higher false sampling links out of 1000 ego-nets rather than 100 as was the case positive rates (1%) the linkage rate becomes signiﬁcant again, par- for Epinions. ticularly for Case 1 links, with success rates of 34.79% (Scheme 1, Figure 9 (Appendix ) illustrates the ROC curves for the Pokec Pokec), 12.29% (Scheme 2, Pokec), 53.45% (Scheme 1, Epinions) network and the AUC. and 64.51% (Scheme 2, Epinions). The linkage rate for the Pokec network under Scheme 2 is the largest for Case 3 links, namely 4.3 Results: Different Training Distribution 13.57% (0.1% FP), and a surprising 45.45% (1% FP). In this section we evaluate the performance of the classiﬁers We conclude that while training on examples from a totally differ- trained on totally different distributions. For this, we turn the classi- ent distribution yields lower true positive rates for equivalent false ﬁer trained on the 100 Epinions ego-nets to classify test data from positive rates, it does not lead to secure conﬁgurations of either ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: cannot

label: paragraph

text: be

text: generalized

text: to

text: other

text: cases

text: or

text: schemes.

text: Table

text: Epinions

label: caption

text: (self-validation):

text: False

text: Positive

text: vs.

text: True

text: Positive

text: for

text: both

text: schemes

text: Table

text: Success

text: percentage

text: for

text: ad-hoc

text: de-anonymization

text: of

text: Scheme

text: for

text: Case

text: node

text: pairs

text: Scheme

text: False

label: table

text: Positive

text: Success

text: percentage

text: Identical

text: Non-identical

text: Epinions

text: Pokec

text: Complete

text: Scheme

text: False

text: Positive

text: The

text: automatic

text: machine

text: learning

text: approach

text: can

text: be

text: generalized

text: to

text: all

text: cases

text: of

text: both

text: schemes,

text: as

text: summarized

text: in

text: Table

text: For

text: the

text: sake

text: of

text: direct

text: comparison,

text: for

text: Scheme

text: using

text: a

text: ﬁxed

text: small

text: false

text: positive

text: rate

text: we

text: can

text: recover

text: of

text: Case

text: links;

text: we

text: also

text: recover

text: of

text: Case

text: links,

text: and

text: of

text: Case

text: links.

text: The

text: attack

text: Complete

text: generalizes

text: to

text: Scheme

text: where

text: we

text: can

text: recover

text: and

text: of

text: links

text: in

text: Cases

text: and

text: respectively.

text: Despite

text: Scheme

text: leading

text: to

text: lower

text: re-identiﬁcation

text: rates,

text: for

text: a

text: ﬁxed

text: false

text: positive

text: rate,

text: Table

text: Pokec

text: (self-validation):

text: False

text: Positive

text: vs.

text: True

text: Positive

text: for

text: we

text: observe

text: they

text: are

text: never

text: negligible,

text: and

text: a

text: released

text: dataset

text: is

text: likely

text: both

text: schemes

text: to

text: lead

text: to

text: the

text: linkage

text: of

text: a

text: signiﬁcant

text: number

text: of

text: individuals

text: between

text: “unlikable”

text: sub-graphs.

text: For

text: even

text: smaller

text: false

text: positives

text: a

text: signiﬁcant

text: number

text: of

text: Case

text: links

text: are

text: recoverable:

text: for

text: Scheme

text: and

text: Scheme

text: for

text: Scheme

text: Case

text: linkage

text: is

text: also

text: never

text: negligible

text: and

text: False

text: Positive

text: higher

text: than

text: for

text: both

text: Schemes.

text: If

text: the

text: adversary

text: has

text: any

text: side

text: information

text: (such

text: as

text: seed

text: nodes)

text: that

text: can

text: be

text: used

text: to

text: establish

text: a

text: good

text: prior,

text: a

text: higher

text: rate

text: of

text: false

text: positives

text: can

text: be

text: tolerated

text: with

text: linkage

text: rates

text: of

text: over

text: even

text: for

text: the

text: hardest

text: Case

text: links.

text: Figure

text: (Appendix

text: illustrates

text: the

text: ROC

text: curves

text: for

text: Scheme

text: and

text: Complete

text: Scheme

text: for

text: all

text: types

text: of

text: node

text: pairs

text: along

text: with

text: area

text: under

text: the

text: ROC

text: Scheme

text: curve

text: (AUC).

text: We

text: note

text: that

text: the

text: AUC

text: for

text: Scheme

text: is

text: consistently

text: above

text: for

text: all

text: link

text: categories,

text: higher

text: than

text: for

text: Scheme

text: for

text: False

text: Positive

text: Cases

text: and

text: This

text: is

text: due

text: to

text: the

text: classiﬁer

text: performing

text: signiﬁcantly

text: better

text: for

text: Scheme

text: when

text: high

text: false

text: positive

text: rates

text: can

text: be

text: tolerated

text: which

text: may

text: or

text: may

text: not

text: be

text: the

text: case

text: depending

text: on

text: adversary

text: side

text: information.

text: Complete

text: Overall,

text: the

text: machine

text: learning

text: approach

text: yields

text: good

text: results

text: for

text: Scheme

text: Cases

text: and

text: which

text: the

text: ad-hoc

text: de-anonymization

text: could

text: not

text: attack.

text: More

text: importantly,

text: it

text: yields

text: good

text: results

text: for

text: Scheme

text: on

text: which

text: the

text: ad-hoc

text: attack

text: was

text: not

text: applicable.

text: As

text: expected,

text: we

text: get

text: Pokec

text: (Table

text: and

text: vice

text: versa,

text: we

text: use

text: the

text: classiﬁer

text: trained

text: on

text: better

text: results

text: for

text: the

text: category

text: of

text: node

text: pairs,

text: and

text: for

text: Scheme

text: Pokec

text: ego-nets

text: to

text: classify

text: the

text: Epinions

text: test

text: data

text: (Table

text: which

text: retain

text: the

text: most

text: information

text: from

text: the

text: original

text: graph.

text: Pokec.

text: The

text: results

text: on

text: the

text: Pokec

text: network

text: are

text: summarized

text: in

text: Table

text: The

text: two

text: networks

text: are

text: of

text: a

text: totally

text: different

text: nature:

text: Epinions

text: is

text: a

text: small

text: web-of-trust

text: on

text: a

text: consumer

text: reviews

text: site;

text: Pokec

text: is

text: a

text: much

text: and

text: are

text: similar

text: to

text: Epinions,

text: which

text: supports

text: the

text: general

text: applicabil-

text: larger

text: national

text: social

text: network.

text: ity

text: of

text: the

text: attack.

text: The

text: ad-hoc

text: attack

text: against

text: Scheme

text: gives

text: almost

text: perfect

text: results.

text: For

text: Case

text: and

text: links

text: the

text: true

text: positive

text: linkage

text: rate

text: It

text: is

text: clear

text: that

text: a

text: different

text: training

text: distribution

text: has

text: a

text: detrimental

text: ef-

text: of

text: the

text: machine

text: learning

text: re-identiﬁcation

text: procedure

text: is

text: and

text: fect

text: on

text: the

text: quality

text: of

text: classiﬁcation

text: for

text: very

text: low

text: false

text: positive

text: values.

text: for

text: Scheme

text: for

text: Scheme

text: they

text: are

text: and

text: re-

text: For

text: a

text: false

text: positive

text: rate

text: of

text: Case

text: and

text: links

text: in

text: the

text: Pokec

text: spectively

text: (for

text: a

text: false

text: positive

text: rate).

text: Interestingly,

text: the

text: linkage

text: network

text: are

text: linked

text: at

text: a

text: rate

text: of

text: and

text: respec-

text: rate

text: for

text: Case

text: which

text: was

text: the

text: lowest

text: in

text: the

text: Epinions

text: network,

text: now

text: tively

text: for

text: Scheme

text: and

text: and

text: for

text: Scheme

text: outperforms

text: Case

text: and

text: is

text: on

text: par

text: with

text: Case

text: when

text: higher

text: false

text: (Table

text: The

text: results

text: on

text: the

text: Epinions

text: network

text: see

text: a

text: similar

text: fall

text: positive

text: rates

text: are

text: tolerable.

text: This

text: is

text: likely

text: due

text: to

text: a

text: lower

text: degree

text: of

text: (Table

text: Despite

text: this,

text: they

text: never

text: become

text: small

text: enough

text: to

text: guar-

text: overlap

text: in

text: the

text: neighborhood

text: of

text: non-identical

text: nodes

text: resulting

text: from

text: antee

text: that

text: the

text: likelihood

text: of

text: linking

text: is

text: negligible.

text: For

text: higher

text: false

text: sampling

text: links

text: out

text: of

text: ego-nets

text: rather

text: than

text: as

text: was

text: the

text: case

text: positive

text: rates

text: the

text: linkage

text: rate

text: becomes

text: signiﬁcant

text: again,

text: par-

text: for

text: Epinions.

text: ticularly

text: for

text: Case

text: links,

text: with

text: success

text: rates

text: of

text: (Scheme

text: Figure

text: (Appendix

text: illustrates

text: the

text: ROC

text: curves

text: for

text: the

text: Pokec

text: Pokec),

text: (Scheme

text: Pokec),

text: (Scheme

text: Epinions)

text: network

text: and

text: the

text: AUC.

text: and

text: (Scheme

text: Epinions).

text: The

text: linkage

text: rate

text: for

text: the

text: Pokec

text: network

text: under

text: Scheme

text: is

text: the

text: largest

text: for

text: Case

text: links,

text: namely

text: Results:

text: Different

text: Training

text: Distribution

text: FP),

text: and

text: a

text: surprising

text: FP).

text: In

text: this

text: section

text: we

text: evaluate

text: the

text: performance

text: of

text: the

text: classiﬁers

text: We

text: conclude

text: that

text: while

text: training

text: on

text: examples

text: from

text: a

text: totally

text: differ-

text: trained

text: on

text: totally

text: different

text: distributions.

text: For

text: this,

text: we

text: turn

text: the

text: classi-

text: ent

text: distribution

text: yields

text: lower

text: true

text: positive

text: rates

text: for

text: equivalent

text: false

text: ﬁer

text: trained

text: on

text: the

text: Epinions

text: ego-nets

text: to

text: classify

text: test

text: data

text: from

text: positive

text: rates,

text: it

text: does

text: not

text: lead

text: to

text: secure

text: conﬁgurations

text: of

text: either

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 8. REFERENCES link prediction, rather than de-anonymization, for the same dataset. In contrast, we do not have directionality available for our graphs [1] L. Backstrom, C. Dwork, and J. Kleinberg. Wherefore art and our feature extraction is simple and efﬁcient, an important factor thou r3579x?: anonymized social networks, hidden patterns, for attacking huge datasets. and structural steganography. In Proceedings of the 16th Our work uses these techniques for the ﬁrst time in an adversar- international conference on World Wide Web, pages 181–190. ial de-anonymization setting: whereas previous de-anonymization ACM, 2007. techniques considered graphs that were organically noisy but struc- [2] V. D. Blondel, M. Esch, C. Chan, F. Clérot, P. Deville, turally intact. In contrast the D4D challenge organizers purposefully E. Huens, F. Morlot, Z. Smoreda, and C. Ziemlicki. Data for and aggressively alter graph topology to prevent linkage. development: the D4D challenge on mobile phone data. CoRR, abs/1210.0137, 2012. [3] L. Breiman. Random forests. Machine learning, 45(1):5–32, 7. CONCLUSION 2001. [4] L. Breiman, J. H. Friedman, R. A. Olshen, and C. J. Stone. Privacy leaks could have serious consequences when they per- Classiﬁcation and regression trees. Wadsworth & Brooks. tain to countries like Ivory Coast which has a history of civil wars Monterey, CA, 1984. and political unrest. Thus carefully evaluating the privacy of data anonymization schemes, such as the ones made available by the [5] A. Criminisi, J. Shotton, and E. Konukoglu. Decision forests D4D competition is imperative. Traditionally such an analysis had for classiﬁcation, regression, density estimation, manifold to be performed manually, and painstakingly repeated for any new learning and semi-supervised learning. Technical Report variant of the anonymization scheme, despite general results indicat- MSR-TR-2011-114, Microsoft Research, Oct 2011. ing social network anonymization schemes are likely to be broken. [6] A. Criminisi, J. Shotton, D. Robertson, and E. Konukoglu. Our approach bypasses the need for manual effort, and can uncover Regression forests for efﬁcient anatomy detection and artefacts of the anonymization process just using examples that al- localization in CT studies. In Medical Computer Vision. low to re-linking nodes in “anonymized” networks. Recognition Techniques and Applications in Medical Imaging, In terms of the speciﬁc anonymization procedures for the D4D pages 106–117. Springer, 2011. competition motivating this study: we do conclude that Scheme 2 [7] C. Dwork and M. Naor. On the difﬁculties of disclosure is marginally harder to de-anonymize and re-link than the original prevention in statistical databases or the case for differential Scheme 1 we evaluated. Despite this, neither provide a level of privacy. Journal of Privacy and Conﬁdentiality, 2(1):8, 2008. privacy we would recommend for public release of data. Even a [8] M. Hay, G. Miklau, D. Jensen, D. Towsley, and P. Weis. reliable linkage rate of 1% would lead to a signiﬁcant fraction of the Resisting structural re-identiﬁcation in anonymized social mobile operator customers being potentially linked. Big data makes networks. Proc. VLDB Endow., 1(1):102–114, Aug. 2008. even a relatively low probability linkage events a certainty. In fact [9] T. K. Ho. Random decision forests. In Document Analysis for a number of realistic conﬁgurations we show the linkage rate was and Recognition, 1995., Proceedings of the Third much higher, leading to efﬁcient attacks particularly if some side International Conference on, volume 1, pages 278–282. information is available to build good priors and tolerate slightly IEEE, 1995. higher false positives. Thus we are relieved that the competition [10] T. K. Ho. The random subspace method for constructing only released such data under conﬁdentiality agreements. decision forests. Pattern Analysis and Machine Intelligence, The approach, and learning task we rely upon, to link or de- IEEE Transactions on, 20(8):832–844, 1998. anonymize, are purposefully simple: it only uses the graph topol- [11] D. Kifer and A. Machanavajjhala. No free lunch in data ogy, not attributes, directionality or multiple snapshots of graphs privacy. In Proceedings of the 2011 ACM SIGMOD over time, despite the availability of such data in some cases. It also International Conference on Management of Data, SIGMOD considers a single pass of the procedure, where no known seeds ’11, pages 193–204, New York, NY, USA, 2011. ACM. are available. It is clear that richer features could be used, and the [12] A. Mislove, M. Marcon, K. P. Gummadi, P. Druschel, and attack can be iterated once a handful of nodes have been uncovered B. Bhattacharjee. Measurement and analysis of online social to unravel larger graphs. These could be topics for future work, and networks. In IMC ’07: Proceedings of the 7th ACM perfecting such attacks could be a fruitful research ﬁeld for years. SIGCOMM conference on Internet measurement, pages However, pursuing too far such a research program may yield 29–42, New York, NY, USA, 2007. ACM. diminishing returns. Our results conﬁrm previous wisdom that [13] Y. D. Mulder, G. Danezis, L. Batina, and B. Preneel. releasing anonymized social networks is likely to, either result in Identiﬁcation via location-proﬁling in GSM networks. In privacy catastrophe, or very poor utility. This paper demonstrates V. Atluri and M. Winslett, editors, WPES, pages 23–32. that even an automated algorithm can produce good enough de- ACM, 2008. anonymization attacks. Thus, it may be more beneﬁcial to research [14] A. Narayanan, E. Shi, and B. Rubinstein. Link prediction by instead alternative ways to perform social network analysis in a de-anonymization: How we won the Kaggle social network privacy friendly manner, and without the need for “anonymized” challenge. In Neural Networks (IJCNN), The 2011 graphs. International Joint Conference on, pages 1825–1834. IEEE, Acknowledgments. We thank Professor Vincent Blondel and Or- 2011. ange for giving us the opportunity to study the anonymiation strat- [15] A. Narayanan and V. Shmatikov. Robust de-anonymization of egy for D4D. The authors would like to thank Pushmeet Kohli and large sparse datasets. In Security and Privacy, 2008. SP 2008. Jamie Shotton for advice on machine learning, as well as Rebecca IEEE Symposium on, pages 111–125. IEEE, 2008. Murphy, Richard Clayton and Steven Murdoch for comments on the [16] A. Narayanan and V. Shmatikov. De-anonymizing social draft manuscripts. This work was supported by the Engineering and networks. In Security and Privacy, 2009 30th IEEE Physical Sciences Research Council [grant number EP/J500665/1]; Symposium on, pages 173–187. IEEE, 2009. and Microsoft Research through its PhD Scholarship Programme. [17] A. Sala, X. Zhao, C. Wilson, H. Zheng, and B. Zhao. Sharing

label: reference

text: REFERENCES

text: link

text: prediction,

text: rather

text: than

text: de-anonymization,

text: for

text: the

text: same

text: dataset.

text: In

text: contrast,

text: we

text: do

text: not

text: have

text: directionality

text: available

text: for

text: our

text: graphs

text: L.

text: Backstrom,

text: C.

text: Dwork,

text: and

text: J.

text: Kleinberg.

text: Wherefore

text: art

text: and

text: our

text: feature

text: extraction

text: is

text: simple

text: and

text: efﬁcient,

text: an

text: important

text: factor

text: thou

text: anonymized

text: social

text: networks,

text: hidden

text: patterns,

text: for

text: attacking

text: huge

text: datasets.

text: and

text: structural

text: steganography.

text: In

text: Proceedings

text: of

text: the

text: Our

text: work

text: uses

text: these

text: techniques

text: for

text: the

text: ﬁrst

text: time

text: in

text: an

text: adversar-

text: international

text: conference

text: on

text: World

text: Wide

text: Web,

text: pages

text: ial

text: de-anonymization

text: setting:

text: whereas

text: previous

text: de-anonymization

text: ACM,

text: techniques

text: considered

text: graphs

text: that

text: were

text: organically

text: noisy

text: but

text: struc-

text: V.

text: D.

text: Blondel,

text: M.

text: Esch,

text: C.

text: Chan,

text: F.

text: Clérot,

text: P.

text: Deville,

text: turally

text: intact.

text: In

text: contrast

text: the

text: challenge

text: organizers

text: purposefully

text: E.

text: Huens,

text: F.

text: Morlot,

text: Z.

text: Smoreda,

text: and

text: C.

text: Ziemlicki.

text: Data

text: for

text: and

text: aggressively

text: alter

text: graph

text: topology

text: to

text: prevent

text: linkage.

text: development:

text: the

text: challenge

text: on

text: mobile

text: phone

text: data.

text: CoRR,

text: L.

text: Breiman.

text: Random

text: forests.

text: Machine

text: learning,

text: CONCLUSION

text: L.

text: Breiman,

text: J.

text: H.

text: Friedman,

text: R.

text: A.

text: Olshen,

text: and

text: C.

text: J.

text: Stone.

text: Privacy

text: leaks

text: could

text: have

text: serious

text: consequences

text: when

text: they

text: per-

text: Classiﬁcation

text: and

text: regression

text: trees.

text: Wadsworth

text: Brooks.

text: tain

text: to

text: countries

text: like

text: Ivory

text: Coast

text: which

text: has

text: a

text: history

text: of

text: civil

text: wars

text: Monterey,

text: CA,

text: and

text: political

text: unrest.

text: Thus

text: carefully

text: evaluating

text: the

text: privacy

text: of

text: data

text: anonymization

text: schemes,

text: such

text: as

text: the

text: ones

text: made

text: available

text: by

text: the

text: A.

text: Criminisi,

text: J.

text: Shotton,

text: and

text: E.

text: Konukoglu.

text: Decision

text: forests

text: competition

text: is

text: imperative.

text: Traditionally

text: such

text: an

text: analysis

text: had

text: for

text: classiﬁcation,

text: regression,

text: density

text: estimation,

text: manifold

text: to

text: be

text: performed

text: manually,

text: and

text: painstakingly

text: repeated

text: for

text: any

text: new

text: learning

text: and

text: semi-supervised

text: learning.

text: Technical

text: Report

text: variant

text: of

text: the

text: anonymization

text: scheme,

text: despite

text: general

text: results

text: indicat-

text: Microsoft

text: Research,

text: Oct

text: ing

text: social

text: network

text: anonymization

text: schemes

text: are

text: likely

text: to

text: be

text: broken.

text: A.

text: Criminisi,

text: J.

text: Shotton,

text: D.

text: Robertson,

text: and

text: E.

text: Konukoglu.

text: Our

text: approach

text: bypasses

text: the

text: need

text: for

text: manual

text: effort,

text: and

text: can

text: uncover

text: Regression

text: forests

text: for

text: efﬁcient

text: anatomy

text: detection

text: and

text: artefacts

text: of

text: the

text: anonymization

text: process

text: just

text: using

text: examples

text: that

text: al-

text: localization

text: in

text: CT

text: studies.

text: In

text: Medical

text: Computer

text: Vision.

text: low

text: to

text: re-linking

text: nodes

text: in

text: “anonymized”

text: networks.

text: Recognition

text: Techniques

text: and

text: Applications

text: in

text: Medical

text: Imaging,

text: In

text: terms

text: of

text: the

text: speciﬁc

text: anonymization

text: procedures

text: for

text: the

text: pages

text: Springer,

text: competition

text: motivating

text: this

text: study:

text: we

text: do

text: conclude

text: that

text: Scheme

text: C.

text: Dwork

text: and

text: M.

text: Naor.

text: On

text: the

text: difﬁculties

text: of

text: disclosure

text: is

text: marginally

text: harder

text: to

text: de-anonymize

text: and

text: re-link

text: than

text: the

text: original

text: prevention

text: in

text: statistical

text: databases

text: or

text: the

text: case

text: for

text: differential

text: Scheme

text: we

text: evaluated.

text: Despite

text: this,

text: neither

text: provide

text: a

text: level

text: of

text: privacy.

text: Journal

text: of

text: Privacy

text: and

text: Conﬁdentiality,

text: privacy

text: we

text: would

text: recommend

text: for

text: public

text: release

text: of

text: data.

text: Even

text: a

text: M.

text: Hay,

text: G.

text: Miklau,

text: D.

text: Jensen,

text: D.

text: Towsley,

text: and

text: P.

text: Weis.

text: reliable

text: linkage

text: rate

text: of

text: would

text: lead

text: to

text: a

text: signiﬁcant

text: fraction

text: of

text: the

text: Resisting

text: structural

text: re-identiﬁcation

text: in

text: anonymized

text: social

text: mobile

text: operator

text: customers

text: being

text: potentially

text: linked.

text: Big

text: data

text: makes

text: networks.

text: Proc.

text: VLDB

text: Endow.,

text: Aug.

text: even

text: a

text: relatively

text: low

text: probability

text: linkage

text: events

text: a

text: certainty.

text: In

text: fact

text: T.

text: K.

text: Ho.

text: Random

text: decision

text: forests.

text: In

text: Document

text: Analysis

text: for

text: a

text: number

text: of

text: realistic

text: conﬁgurations

text: we

text: show

text: the

text: linkage

text: rate

text: was

text: and

text: Recognition,

text: Proceedings

text: of

text: the

text: Third

text: much

text: higher,

text: leading

text: to

text: efﬁcient

text: attacks

text: particularly

text: if

text: some

text: side

text: International

text: Conference

text: on,

text: volume

text: pages

text: information

text: is

text: available

text: to

text: build

text: good

text: priors

text: and

text: tolerate

text: slightly

text: IEEE,

text: higher

text: false

text: positives.

text: Thus

text: we

text: are

text: relieved

text: that

text: the

text: competition

text: T.

text: K.

text: Ho.

text: The

text: random

text: subspace

text: method

text: for

text: constructing

text: only

text: released

text: such

text: data

text: under

text: conﬁdentiality

text: agreements.

text: decision

text: forests.

text: Pattern

text: Analysis

text: and

text: Machine

text: Intelligence,

text: The

text: approach,

text: and

text: learning

text: task

text: we

text: rely

text: upon,

text: to

text: link

text: or

text: de-

text: IEEE

text: Transactions

text: on,

text: anonymize,

text: are

text: purposefully

text: simple:

text: it

text: only

text: uses

text: the

text: graph

text: topol-

text: D.

text: Kifer

text: and

text: A.

text: Machanavajjhala.

text: No

text: free

text: lunch

text: in

text: data

text: ogy,

text: not

text: attributes,

text: directionality

text: or

text: multiple

text: snapshots

text: of

text: graphs

text: privacy.

text: In

text: Proceedings

text: of

text: the

text: ACM

text: SIGMOD

text: over

text: time,

text: despite

text: the

text: availability

text: of

text: such

text: data

text: in

text: some

text: cases.

text: It

text: also

text: International

text: Conference

text: on

text: Management

text: of

text: Data,

text: SIGMOD

text: considers

text: a

text: single

text: pass

text: of

text: the

text: procedure,

text: where

text: no

text: known

text: seeds

text: pages

text: New

text: York,

text: NY,

text: USA,

text: ACM.

text: are

text: available.

text: It

text: is

text: clear

text: that

text: richer

text: features

text: could

text: be

text: used,

text: and

text: the

text: A.

text: Mislove,

text: M.

text: Marcon,

text: K.

text: P.

text: Gummadi,

text: P.

text: Druschel,

text: and

text: attack

text: can

text: be

text: iterated

text: once

text: a

text: handful

text: of

text: nodes

text: have

text: been

text: uncovered

text: B.

text: Bhattacharjee.

text: Measurement

text: and

text: analysis

text: of

text: online

text: social

text: to

text: unravel

text: larger

text: graphs.

text: These

text: could

text: be

text: topics

text: for

text: future

text: work,

text: and

text: networks.

text: In

text: IMC

text: Proceedings

text: of

text: the

text: ACM

text: perfecting

text: such

text: attacks

text: could

text: be

text: a

text: fruitful

text: research

text: ﬁeld

text: for

text: years.

text: SIGCOMM

text: conference

text: on

text: Internet

text: measurement,

text: pages

text: However,

text: pursuing

text: too

text: far

text: such

text: a

text: research

text: program

text: may

text: yield

text: New

text: York,

text: NY,

text: USA,

text: ACM.

text: diminishing

text: returns.

text: Our

text: results

text: conﬁrm

text: previous

text: wisdom

text: that

text: Y.

text: D.

text: Mulder,

text: G.

text: Danezis,

text: L.

text: Batina,

text: and

text: B.

text: Preneel.

text: releasing

text: anonymized

text: social

text: networks

text: is

text: likely

text: to,

text: either

text: result

text: in

text: Identiﬁcation

text: via

text: location-proﬁling

text: in

text: GSM

text: networks.

text: In

text: privacy

text: catastrophe,

text: or

text: very

text: poor

text: utility.

text: This

text: paper

text: demonstrates

text: V.

text: Atluri

text: and

text: M.

text: Winslett,

text: editors,

text: WPES,

text: pages

text: that

text: even

text: an

text: automated

text: algorithm

text: can

text: produce

text: good

text: enough

text: de-

text: ACM,

text: anonymization

text: attacks.

text: Thus,

text: it

text: may

text: be

text: more

text: beneﬁcial

text: to

text: research

text: A.

text: Narayanan,

text: E.

text: Shi,

text: and

text: B.

text: Rubinstein.

text: Link

text: prediction

text: by

text: instead

text: alternative

text: ways

text: to

text: perform

text: social

text: network

text: analysis

text: in

text: a

text: de-anonymization:

text: How

text: we

text: won

text: the

text: Kaggle

text: social

text: network

text: privacy

text: friendly

text: manner,

text: and

text: without

text: the

text: need

text: for

text: “anonymized”

text: challenge.

text: In

text: Neural

text: Networks

text: (IJCNN),

text: The

text: graphs.

text: International

text: Joint

text: Conference

text: on,

text: pages

text: IEEE,

text: Acknowledgments.

text: We

text: thank

text: Professor

text: Vincent

text: Blondel

text: and

text: Or-

text: ange

text: for

text: giving

text: us

text: the

text: opportunity

text: to

text: study

text: the

text: anonymiation

text: strat-

text: A.

text: Narayanan

text: and

text: V.

text: Shmatikov.

text: Robust

text: de-anonymization

text: of

text: egy

text: for

text: The

text: authors

text: would

text: like

text: to

text: thank

text: Pushmeet

text: Kohli

text: and

text: large

text: sparse

text: datasets.

text: In

text: Security

text: and

text: Privacy,

text: SP

text: Jamie

text: Shotton

text: for

text: advice

text: on

text: machine

text: learning,

text: as

text: well

text: as

text: Rebecca

text: IEEE

text: Symposium

text: on,

text: pages

text: IEEE,

text: Murphy,

text: Richard

text: Clayton

text: and

text: Steven

text: Murdoch

text: for

text: comments

text: on

text: the

text: A.

text: Narayanan

text: and

text: V.

text: Shmatikov.

text: De-anonymizing

text: social

text: draft

text: manuscripts.

text: This

text: work

text: was

text: supported

text: by

text: the

text: Engineering

text: and

text: networks.

text: In

text: Security

text: and

text: Privacy,

text: IEEE

text: Physical

text: Sciences

text: Research

text: Council

text: [grant

text: number

text: Symposium

text: on,

text: pages

text: IEEE,

text: and

text: Microsoft

text: Research

text: through

text: its

text: PhD

text: Scholarship

text: Programme.

text: A.

text: Sala,

text: X.

text: Zhao,

text: C.

text: Wilson,

text: H.

text: Zheng,

text: and

text: B.

text: Zhao.

text: Sharing


text: professionals, to discuss novel ways of exploiting web-based technologies for astronomy research or public engage- ment. Since 2009 .Astronomy has included a Hack Day, and in recent years astronomy-themed Hack Days have taken place at the annual conferences of the American Astronomical Society and the UK National Astronomy Meeting. With an increasing number of robotic telescopes coming online and the advent of mega-facilities such as Gaia, the Large Synoptic Survey Telescope (LSST), and the Square Kilometer Array, control strategies, software and intelligent data processing form an increasingly important part of astronomical observatories. With the SPIE Hack Day, our aim was to provide an opportunity for instrumentation professionals to share skills and collaborate outside of the normal boundaries of an instrumentation project. 2. ON THE DAY The Hack Day took place on Thursday 26 June over an entire day. Whilst we gathered contact details in the weeks beforehand via an online sign-up form, there was no formal registration procedure, the event was open and free of charge to all conference participants. Lunch and refreshments were provided free of charge. The format was unscheduled, with no formal presentations, as is traditional for such events. At the start of the day, we gave participants the opportunity to introduce themselves and present what ideas or problems they were interested in working on during the event. Likewise, the day was ended with the participants describing and showcasing the hacks they worked on during the day. In the following section, we highlight some selected Hack Day projects. The names listed alongside the hacks are the participants who proposed and led the project, however many hacks were team-based eﬀorts. 3. HACK DAY PROJECTS 3.1 Soniﬁcation of astronomical spectra (J. Gilbert) A frequent theme at astronomy hack days is to discover innovative ways of representing astronomical datasets to aid data discovery. One non-traditional avenue is to convert data to sound. This hack aimed to convert astronomical spectra into music; the ability to convert data from a visual into an auditory medium , as well as presenting a creative challenge, can be useful for communicating astronomy to visually impaired people. The main challenge was to discover how to link the typical characteristics of spectra (e.g. absolute wavelength range, important lines, continuum level vs transients etc.) to the main aspects of a musical piece (time signature, tempo, key, major/minor, pitch); and to do so in a robust way so that spectra which look similar will also sound similar. James wrote a number of routines to quantify these characteristics and link them directly to the musical parameters; then generated a short, loopable tune. An important goal is to make sure we can deﬁnitely ‘hear’ the emission/absorption lines of the object, and for the sound to be attractive. 3.2 A telescope control system for Android platforms (P. Kub´anek) RTS2, or Remote Telescope System, 2nd Version, is an open source observatory control software. It allows astronomers around the world to let the machines control their observatories. So they can sleep during the night and work during the day. RTS2 takes care of all duties of a (night) observer - it opens and closes observatory protected cover at evening, morning and in case of bad weather, command telescope to point, ﬁlter wheel to turn and camera to expose. It select the observations from the database, and logs the observations to the database. It is used on more than 20 observatories around the planet, making it one of the most popular observatory control programmes. During the Hack Day, RTS2 creator Petr Kub´anek worked on developing an Android application for the software. 3.3 Making ﬁgures from a textbook interactive with MPLD3 and d3.js (M. Gully-Santiago) A growing theme in modern astrophysics is the growth of the Volume, Variety, and Velocity of astronomical data.5 Particularly, the increasing multi-dimensionality of large astronomical datasets is giving rise to new data visualization techniques.2 Michael Gully-Santiago’s hack was aimed at transforming static ﬁgures to interactive ﬁgures for web browsers. The starting static ﬁgure was a single panel of Figure 10.21 of the textbook “Statistics, Data Mining, and Machine Learning in Astronomy: A Practical Python Guide” [6, hereafter ICVG]. The

text: professionals,

text: to

text: discuss

text: novel

text: ways

text: of

text: exploiting

text: web-based

text: technologies

text: for

text: astronomy

text: research

text: or

text: public

text: engage-

text: ment.

text: Since

text: .Astronomy

text: has

text: included

text: a

text: Hack

text: Day,

text: and

text: in

text: recent

text: years

text: astronomy-themed

text: Hack

text: Days

text: have

text: taken

text: place

text: at

text: the

text: annual

text: conferences

text: of

text: the

text: American

text: Astronomical

text: Society

text: and

text: the

text: UK

text: National

text: Astronomy

text: Meeting.

text: With

text: an

text: increasing

text: number

text: of

text: robotic

text: telescopes

text: coming

text: online

text: and

text: the

text: advent

text: of

text: mega-facilities

text: such

text: as

text: Gaia,

text: the

text: Large

text: Synoptic

text: Survey

text: Telescope

text: (LSST),

text: and

text: the

text: Square

text: Kilometer

text: Array,

text: control

text: strategies,

text: software

text: and

text: intelligent

text: data

text: processing

text: form

text: an

text: increasingly

text: important

text: part

text: of

text: astronomical

text: observatories.

text: With

text: the

text: SPIE

text: Hack

text: Day,

text: our

text: aim

text: was

text: to

text: provide

text: an

text: opportunity

text: for

text: instrumentation

text: professionals

text: to

text: share

text: skills

text: and

text: collaborate

text: outside

text: of

text: the

text: normal

text: boundaries

text: of

text: an

text: instrumentation

text: project.

text: ON

text: THE

text: DAY

text: The

text: Hack

text: Day

text: took

text: place

text: on

text: Thursday

text: June

text: over

text: an

text: entire

text: day.

text: Whilst

text: we

text: gathered

text: contact

text: details

text: in

text: the

text: weeks

text: beforehand

text: via

text: an

text: online

text: sign-up

text: form,

text: there

text: was

text: no

text: formal

text: registration

text: procedure,

text: the

text: event

text: was

text: open

text: and

text: free

text: of

text: charge

text: to

text: all

text: conference

text: participants.

text: Lunch

text: and

text: refreshments

text: were

text: provided

text: free

text: of

text: charge.

text: The

text: format

text: was

text: unscheduled,

text: with

text: no

text: formal

text: presentations,

text: as

text: is

text: traditional

text: for

text: such

text: events.

text: At

text: the

text: start

text: of

text: the

text: day,

text: we

text: gave

text: participants

text: the

text: opportunity

text: to

text: introduce

text: themselves

text: and

text: present

text: what

text: ideas

text: or

text: problems

text: they

text: were

text: interested

text: in

text: working

text: on

text: during

text: the

text: event.

text: Likewise,

text: the

text: day

text: was

text: ended

text: with

text: the

text: participants

text: describing

text: and

text: showcasing

text: the

text: hacks

text: they

text: worked

text: on

text: during

text: the

text: day.

text: In

text: the

text: following

text: section,

text: we

text: highlight

text: some

text: selected

text: Hack

text: Day

text: projects.

text: The

text: names

text: listed

text: alongside

text: the

text: hacks

text: are

text: the

text: participants

text: who

text: proposed

text: and

text: led

text: the

text: project,

text: however

text: many

text: hacks

text: were

text: team-based

text: eﬀorts.

text: HACK

text: DAY

text: PROJECTS

text: Soniﬁcation

text: of

text: astronomical

text: spectra

text: (J.

text: Gilbert)

text: A

text: frequent

text: theme

text: at

text: astronomy

text: hack

text: days

text: is

text: to

text: discover

text: innovative

text: ways

text: of

text: representing

text: astronomical

text: datasets

text: to

text: aid

text: data

text: discovery.

text: One

text: non-traditional

text: avenue

text: is

text: to

text: convert

text: data

text: to

text: sound.

text: This

text: hack

text: aimed

text: to

text: convert

text: astronomical

text: spectra

text: into

text: music;

text: the

text: ability

text: to

text: convert

text: data

text: from

text: a

text: visual

text: into

text: an

text: auditory

text: medium

text: as

text: well

text: as

text: presenting

text: a

text: creative

text: challenge,

text: can

text: be

text: useful

text: for

text: communicating

text: astronomy

text: to

text: visually

text: impaired

text: people.

text: The

text: main

text: challenge

text: was

text: to

text: discover

text: how

text: to

text: link

text: the

text: typical

text: characteristics

text: of

text: spectra

text: (e.g.

text: absolute

text: wavelength

text: range,

text: important

text: lines,

text: continuum

text: level

text: vs

text: transients

text: etc.)

text: to

text: the

text: main

text: aspects

text: of

text: a

text: musical

text: piece

text: (time

text: signature,

text: tempo,

text: key,

text: major/minor,

text: pitch);

text: and

text: to

text: do

text: so

text: in

text: a

text: robust

text: way

text: so

text: that

text: spectra

text: which

text: look

text: similar

text: will

text: also

text: sound

text: similar.

text: James

text: wrote

text: a

text: number

text: of

text: routines

text: to

text: quantify

text: these

text: characteristics

text: and

text: link

text: them

text: directly

text: to

text: the

text: musical

text: parameters;

text: then

text: generated

text: a

text: short,

text: loopable

text: tune.

text: An

text: important

text: goal

text: is

text: to

text: make

text: sure

text: we

text: can

text: deﬁnitely

text: ‘hear’

text: the

text: emission/absorption

text: lines

text: of

text: the

text: object,

text: and

text: for

text: the

text: sound

text: to

text: be

text: attractive.

text: A

text: telescope

text: control

text: system

text: for

text: Android

text: platforms

text: (P.

text: Kub´anek)

text: or

text: Remote

text: Telescope

text: System,

text: Version,

text: is

text: an

text: open

text: source

text: observatory

text: control

text: software.

text: It

text: allows

text: astronomers

text: around

text: the

text: world

text: to

text: let

text: the

text: machines

text: control

text: their

text: observatories.

text: So

text: they

text: can

text: sleep

text: during

text: the

text: night

text: and

text: work

text: during

text: the

text: day.

text: takes

text: care

text: of

text: all

text: duties

text: of

text: a

text: (night)

text: observer

text: it

text: opens

text: and

text: closes

text: observatory

text: protected

text: cover

text: at

text: evening,

text: morning

text: and

text: in

text: case

text: of

text: bad

text: weather,

text: command

text: telescope

text: to

text: point,

text: ﬁlter

text: wheel

text: to

text: turn

text: and

text: camera

text: to

text: expose.

text: It

text: select

text: the

text: observations

text: from

text: the

text: database,

text: and

text: logs

text: the

text: observations

text: to

text: the

text: database.

text: It

text: is

text: used

text: on

text: more

text: than

text: observatories

text: around

text: the

text: planet,

text: making

text: it

text: one

text: of

text: the

text: most

text: popular

text: observatory

text: control

text: programmes.

text: During

text: the

text: Hack

text: Day,

text: creator

text: Petr

text: Kub´anek

text: worked

text: on

text: developing

text: an

text: Android

text: application

text: for

text: the

text: software.

text: Making

text: ﬁgures

text: from

text: a

text: textbook

text: interactive

text: with

text: and

text: (M.

text: Gully-Santiago)

text: A

text: growing

text: theme

text: in

text: modern

text: astrophysics

text: is

text: the

text: growth

text: of

text: the

text: Volume,

text: Variety,

text: and

text: Velocity

text: of

text: astronomical

text: Particularly,

text: the

text: increasing

text: multi-dimensionality

text: of

text: large

text: astronomical

text: datasets

text: is

text: giving

text: rise

text: to

text: new

text: data

text: visualization

text: Michael

text: Gully-Santiago’s

text: hack

text: was

text: aimed

text: at

text: transforming

text: static

text: ﬁgures

text: to

text: interactive

text: ﬁgures

text: for

text: web

text: browsers.

text: The

text: starting

text: static

text: ﬁgure

text: was

text: a

text: single

text: panel

text: of

text: Figure

text: of

text: the

text: textbook

text: “Statistics,

text: Data

text: Mining,

text: and

text: Machine

text: Learning

text: in

text: Astronomy:

text: A

text: Practical

text: Python

text: Guide”

text: hereafter

text: ICVG].

text: The


text: 9. Simpson, R. J. et al, “Unproceedings of the Fourth .Astronomy Conference (Heidelberg, Germany, July 9-11, 2012)”, Arxiv: 1301.5193 (2013)

text: Simpson,

text: R.

text: J.

text: et

text: al,

text: “Unproceedings

text: of

text: the

text: Fourth

text: .Astronomy

text: Conference

text: (Heidelberg,

text: Germany,

text: July

text: Arxiv:


text: 11 | − (cid:48)| for j j > 1. As mentioned above there exist three other sets of R-moves consistent with our S choice of the modular -matrix (2.3). Using one of these in (3.9) would be equivalent to replacing − † † − G with either G 1, U G U or U G 1U with the unitary transformation (3.3) and modifying the j j j j above relations suitably. The BMW algebra contains a copy of the Temperley-Lieb algebra [36] as a subalgebra, from which we can construct the solution to the YBE (cid:104) (cid:105) − R (u) = sinh(γ + u) 1 sinh(u) E , j j − = sinh(γ u) p(1) + sinh(γ + u) p(2) + p(5) j j √ with cosh γ = 5. Expanding of the resulting transfer matrix around u = 0 one obtains the anyon 2 0 model (3.2) with (α(cid:48), α(cid:48)(cid:48)) = ±( √1 , √1 ) for θ = 0 and π. As for other Temperley-Lieb models it 2 2 2 10 can be written as (cid:88) ∓ L H √ 1 = E + const. . 0,π j 10 j=1 Using the full BMW algebra one can ﬁnd two additional solutions to the YBE [37]. One of them is [38, 39] (cid:18) (cid:19) (cid:18) (cid:19) (cid:16) (cid:17) (cid:18)7iπ (cid:19) iπ(cid:18) 1 (cid:19) −(cid:18) − (cid:19)− −(cid:18) (cid:19) Rj(u) = sinh 10 sinh 10 1 + 2 sinh(u) e1iπ0 uGj eu 1iπ0 Gj 1 (cid:18) iπ (cid:19) (cid:18) 3iπ (cid:19) − iπ − 3iπ (1) (2) = sinh u + sinh u + p + sinh u sinh u p (3.10) 10 10 j 10 10 j 9iπ 3iπ (5) + sinh u + sinh u + p . 10 10 j (cid:16) (cid:17) √ − This solution leads to integrable points at θ = η, η + π where η = atan 1+ 5 π. The 4 4 other R-matrix obtained by Baxterization of the BMW representation is related to (3.10) through − − the transformation (3.3) and gives rise to integrable points at θ = η, η + π. However, these integrable points are equivalent to the ones they are mapped from and are subsequently omitted from further analysis. As stated earlier, the weights given by (3.4) will lead to a solution of the YBE and a commuting transfer matrix (3.6). It turns out that this transfer matrix belongs to a family of commuting transfer matrices. To deﬁne these transfer matrices we present the YBE for face weights ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: for

text: j

text: j

text: As

text: mentioned

text: above

text: there

text: exist

text: three

text: other

text: sets

text: of

text: R-moves

text: consistent

text: with

text: our

text: S

text: choice

text: of

text: the

text: modular

text: -matrix

text: Using

text: one

text: of

text: these

text: in

text: would

text: be

text: equivalent

text: to

text: replacing

text: G

text: with

text: either

text: G

text: U

text: G

text: U

text: or

text: U

text: G

text: with

text: the

text: unitary

text: transformation

text: and

text: modifying

text: the

text: j

text: j

text: j

text: j

text: above

text: relations

text: suitably.

text: The

text: BMW

text: algebra

text: contains

text: a

text: copy

text: of

text: the

text: Temperley-Lieb

text: algebra

text: as

text: a

text: subalgebra,

text: from

text: which

text: we

text: can

text: construct

text: the

text: solution

text: to

text: the

text: YBE

text: R

text: (u)

text: sinh(γ

text: u)

text: sinh(u)

text: E

text: j

text: j

text: sinh(γ

text: u)

text: sinh(γ

text: u)

text: j

text: j

text: with

text: cosh

text: γ

text: Expanding

text: of

text: the

text: resulting

text: transfer

text: matrix

text: around

text: u

text: one

text: obtains

text: the

text: anyon

text: model

text: with

text: √1

text: √1

text: for

text: θ

text: and

text: π.

text: As

text: for

text: other

text: Temperley-Lieb

text: models

text: it

text: can

text: be

text: written

text: as

text: L

text: H

text: E

text: const.

text: j

text: Using

text: the

text: full

text: BMW

text: algebra

text: one

text: can

text: ﬁnd

text: two

text: additional

text: solutions

text: to

text: the

text: YBE

text: One

text: of

text: them

text: is

text: Rj(u)

text: sinh

text: sinh

text: sinh(u)

text: uGj

text: eu

text: Gj

text: iπ

text: iπ

text: sinh

text: u

text: sinh

text: u

text: p

text: sinh

text: u

text: sinh

text: u

text: p

text: j

text: j

text: sinh

text: u

text: sinh

text: u

text: p

text: j

text: This

text: solution

text: leads

text: to

text: integrable

text: points

text: at

text: θ

text: η,

text: η

text: π

text: where

text: η

text: atan

text: π.

text: The

text: other

text: R-matrix

text: obtained

text: by

text: Baxterization

text: of

text: the

text: BMW

text: representation

text: is

text: related

text: to

text: through

text: the

text: transformation

text: and

text: gives

text: rise

text: to

text: integrable

text: points

text: at

text: θ

text: η,

text: η

text: π.

text: However,

text: these

text: integrable

text: points

text: are

text: equivalent

text: to

text: the

text: ones

text: they

text: are

text: mapped

text: from

text: and

text: are

text: subsequently

text: omitted

text: from

text: further

text: analysis.

text: As

text: stated

text: earlier,

text: the

text: weights

text: given

text: by

text: will

text: lead

text: to

text: a

text: solution

text: of

text: the

text: YBE

text: and

text: a

text: commuting

text: transfer

text: matrix

text: It

text: turns

text: out

text: that

text: this

text: transfer

text: matrix

text: belongs

text: to

text: a

text: family

text: of

text: commuting

text: transfer

text: matrices.

text: To

text: deﬁne

text: these

text: transfer

text: matrices

text: we

text: present

text: the

text: YBE

text: for

text: face

text: weights

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 14 In this expression, the c are complex constants while the f (u) with the following properties: d d L (i) they are analytic functions, (ii) their ﬁnite zeroes converge to a set of n = O( ) complex numbers for suﬃciently large d and (iii) they cycle, as a function of d, with period p = 1, 2 or 3 depending on the eigenvalue Λ (u) used as a seed in the recursion (4.2), i.e. f (u) = f (u). This 2 d+p d → ∞ generalizes the observation for spin-1/2 chains where the d limit of the functions Λ (u) has d been found to exist (corresponding to a cycle with p = 1) and is related to the eigenvalues of the so-called Q-operator [44, 45]. The periodicity in d allows to rewrite the recursion relation (4.2) in (cid:81) (cid:39) ≡ terms of a linear combination q (u) of the functions f (u) to f − (u) such that q (u) ζdq(u) d d d+p 1 d − → ∞ ζd n sinh(u u + γ ) for d . As a result the spectral problem can be formulated as a (cid:96)=1 (cid:96) 2 so-called T Q-equation [2] − L − L Λ(u) q(u) = ζ 1[sinh(u + γ)] q(u γ) + ζ [sinh(u)] q(u + γ) . (4.4) { } As a consequence of the analyticity of the transfer matrix eigenvalues Λ(u) the zeroes u n (cid:96) (cid:96)=1 of the q-functions are solutions to the Bethe equations (4.1). In terms of these Bethe roots energy and momentum of the corresponding state is given by (cid:40) (cid:41) (cid:88) ± √1 L √1 n 1 (cid:18) (cid:19) E = 2 + (cid:88) − 2 2 2 5 k=1 sinh(uk γ2)−sinh(uk + γ2) (4.5) − Λ(0) n sinh(u γ ) P = i log L = i log k 2 + i log ζ . sinh γ k=1 sinh(uk + γ2) With the expression (4.4) for the spectrum of the transfer matrix, the value of the twist corre- → ±∞ sponding to a given eigenvalue can be obtained from its asymptotics as u : computing the   (cid:32) (cid:33) eigenvalues λ± of the operators  (cid:112)  L 2 ∓ t± = →lim±∞ ± e u t(u) u φ 1 L for chains with up to = 10 sites we ﬁnd that they take values (cid:26) (cid:18) (cid:19) (cid:12) (cid:27) (cid:110) (cid:111) (cid:12) (cid:12) (cid:12) √ L ∈ ± ± ∪ ± iπ ≤ ≤ λ± 0, 1, 5 2 cosh kγ l 0 l k = 1, . . . , . (4.6) k 2 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: In

text: this

text: expression,

text: the

text: c

text: are

text: complex

text: constants

text: while

text: the

text: f

text: (u)

text: with

text: the

text: following

text: properties:

text: d

text: d

text: L

text: (i)

text: they

text: are

text: analytic

text: functions,

text: (ii)

text: their

text: ﬁnite

text: zeroes

text: converge

text: to

text: a

text: set

text: of

text: n

text: O(

text: complex

text: numbers

text: for

text: suﬃciently

text: large

text: d

text: and

text: (iii)

text: they

text: cycle,

text: as

text: a

text: function

text: of

text: d,

text: with

text: period

text: p

text: or

text: depending

text: on

text: the

text: eigenvalue

text: Λ

text: (u)

text: used

text: as

text: a

text: seed

text: in

text: the

text: recursion

text: i.e.

text: f

text: (u)

text: f

text: (u).

text: This

text: d+p

text: d

text: generalizes

text: the

text: observation

text: for

text: chains

text: where

text: the

text: d

text: limit

text: of

text: the

text: functions

text: Λ

text: (u)

text: has

text: d

text: been

text: found

text: to

text: exist

text: (corresponding

text: to

text: a

text: cycle

text: with

text: p

text: and

text: is

text: related

text: to

text: the

text: eigenvalues

text: of

text: the

text: so-called

text: Q-operator

text: The

text: periodicity

text: in

text: d

text: allows

text: to

text: rewrite

text: the

text: recursion

text: relation

text: in

text: terms

text: of

text: a

text: linear

text: combination

text: q

text: (u)

text: of

text: the

text: functions

text: f

text: (u)

text: to

text: f

text: (u)

text: such

text: that

text: q

text: (u)

text: ζdq(u)

text: d

text: d

text: d+p

text: d

text: ζd

text: n

text: sinh(u

text: u

text: γ

text: for

text: d

text: As

text: a

text: result

text: the

text: spectral

text: problem

text: can

text: be

text: formulated

text: as

text: a

text: so-called

text: T

text: Q-equation

text: L

text: L

text: Λ(u)

text: q(u)

text: ζ

text: γ)]

text: q(u

text: γ)

text: ζ

text: [sinh(u)]

text: q(u

text: γ)

text: As

text: a

text: consequence

text: of

text: the

text: analyticity

text: of

text: the

text: transfer

text: matrix

text: eigenvalues

text: Λ(u)

text: the

text: zeroes

text: u

text: n

text: of

text: the

text: q-functions

text: are

text: solutions

text: to

text: the

text: Bethe

text: equations

text: In

text: terms

text: of

text: these

text: Bethe

text: roots

text: energy

text: and

text: momentum

text: of

text: the

text: corresponding

text: state

text: is

text: given

text: by

text: √1

text: L

text: √1

text: n

text: E

text: sinh(uk

text: n

text: sinh(u

text: γ

text: P

text: i

text: log

text: L

text: i

text: log

text: k

text: i

text: log

text: ζ

text: sinh

text: γ

text: sinh(uk

text: With

text: the

text: expression

text: for

text: the

text: spectrum

text: of

text: the

text: transfer

text: matrix,

text: the

text: value

text: of

text: the

text: twist

text: corre-

text: sponding

text: to

text: a

text: given

text: eigenvalue

text: can

text: be

text: obtained

text: from

text: its

text: asymptotics

text: as

text: u

text: computing

text: the

text: eigenvalues

text: λ±

text: of

text: the

text: operators

text: L

text: t±

text: →lim±∞

text: e

text: u

text: t(u)

text: u

text: φ

text: L

text: for

text: chains

text: with

text: up

text: to

text: sites

text: we

text: ﬁnd

text: that

text: they

text: take

text: values

text: L

text: iπ

text: λ±

text: cosh

text: kγ

text: l

text: l

text: k

text: k

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 3 extended symmetries associated to the Lie algebras B = SO(5) and D = SO(10), respectively. 2 5 To present our results in a self-contained way, some general facts on the classiﬁcation and spectral W data of the relevant minimal models of Casimir-type -algebras are included in Appendix . For the anti-ferromagnetic anyon chain we propose a modular invariant partition function in terms of W the Virasoro characters of the irreducible highest weight representations of the D (9, 10) RCFT. 5 S The -matrix and fusion rules of this CFT are given in Appendix . II. SO(5) ANYONS 2 Algebraically, anyonic theories can be described by braided tensor categories [8, 30, 31]. A { } braided tensor category consists of a collection of objects ψ (including an identity) equipped i with a tensor product (fusion rules), (cid:77) ∼ ⊗ ψ ψ = Nc ψ a b ab c c ∈ { } where Nc are non-negative integers. In the special case Nc 0, 1 it is called multiplicity ab ab free. Below we shall use a graphical representation of ’fusion states’ of the anyon model where vertices a b c may occur provided that ψ appears in the fusion of ψ and ψ . We require associativity in our c a b fusion i.e. ∼ ⊗ ⊗ ⊗ ⊗ (ψ ψ ) ψ = ψ (ψ ψ ), a b c a b c which is governed by F -moves, also referred to as generalized 6j-symbols, (cid:80) b c b c (cid:48) a d e = d(cid:48)(Feabc)dd(cid:48) a d e (2.1) ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: extended

text: symmetries

text: associated

text: to

text: the

text: Lie

text: algebras

text: B

text: and

text: D

text: respectively.

text: To

text: present

text: our

text: results

text: in

text: a

text: self-contained

text: way,

text: some

text: general

text: facts

text: on

text: the

text: classiﬁcation

text: and

text: spectral

text: W

text: data

text: of

text: the

text: relevant

text: minimal

text: models

text: of

text: Casimir-type

text: -algebras

text: are

text: included

text: in

text: Appendix

text: For

text: the

text: anti-ferromagnetic

text: anyon

text: chain

text: we

text: propose

text: a

text: modular

text: invariant

text: partition

text: function

text: in

text: terms

text: of

text: W

text: the

text: Virasoro

text: characters

text: of

text: the

text: irreducible

text: highest

text: weight

text: representations

text: of

text: the

text: D

text: RCFT.

text: S

text: The

text: -matrix

text: and

text: fusion

text: rules

text: of

text: this

text: CFT

text: are

text: given

text: in

text: Appendix

text: II.

label: section

text: ANYONS

text: Algebraically,

text: anyonic

text: theories

text: can

text: be

text: described

text: by

text: braided

text: tensor

text: categories

text: A

text: braided

text: tensor

text: category

text: consists

text: of

text: a

text: collection

text: of

text: objects

text: ψ

text: (including

text: an

text: identity)

text: equipped

text: i

text: with

text: a

text: tensor

text: product

text: (fusion

text: rules),

text: ψ

text: ψ

text: Nc

text: ψ

text: a

text: b

text: ab

text: c

text: c

text: where

text: Nc

text: are

text: non-negative

text: integers.

text: In

text: the

text: special

text: case

text: Nc

text: it

text: is

text: called

text: multiplicity

text: ab

text: ab

text: free.

text: Below

text: we

text: shall

text: use

text: a

text: graphical

text: representation

text: of

text: ’fusion

text: states’

text: of

text: the

text: anyon

text: model

text: where

text: vertices

text: a

text: b

text: c

text: may

text: occur

text: provided

text: that

text: ψ

text: appears

text: in

text: the

text: fusion

text: of

text: ψ

text: and

text: ψ

text: We

text: require

text: associativity

text: in

text: our

text: c

text: a

text: b

text: fusion

text: i.e.

text: (ψ

text: ψ

text: ψ

text: ψ

text: (ψ

text: ψ

text: a

text: b

text: c

text: a

text: b

text: c

text: which

text: is

text: governed

text: by

text: F

text: -moves,

text: also

text: referred

text: to

text: as

text: generalized

text: b

text: c

text: b

text: c

text: a

text: d

text: e

text: a

text: d

text: e

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 23 − This allows us to determine the scaling dimensions X = h + h¯ and conformal spins s = h h¯ of the primary ﬁelds present in the CFT from the spectrum of the lattice model (n, n¯ are non- negative integers). Solving the Bethe equations numerically for root conﬁgurations corresponding to a particular excitation for various lattice sizes we obtain a sequence of ﬁnite size estimations for the scaling dimensions (cid:16) (cid:17) L L L − L Xnum( ) = E( ) E(0)( ) . (5.3) θ 2πv F This sequence is then extrapolated to obtain a numerical approximation Xext to the scaling θ dimension, which is subsequently identiﬁed with a pair (h, h¯) of conformal weights. Similarly, the central charge can be computed by ﬁnite size scaling analysis of the ground state energy based on (5.1). A. The BMW model at θ = η Solving the Bethe equations for the ground state conﬁguration of 4-strings in systems with even L we ﬁnd the scaling of the ground state energy L − L− L− E(0)( ) = E(0) 0.6114471233 1 + o( 1) . θ=η This implies that the central charge is c = 1.14285(1), predicted to be actually 8 in agreement with 7 the ferromagnetic Z Fateev-Zamolodchikov model. This central charge appears in several rational 5 W CFTs from the minimal series of Casimir-type -algebras, see Appendix . Restricting ourselves to unitary ones these are W A : (2, 3, 4, 5) c (6, 7) , 4 A4 W B : (2, 4) c (5, 7) , 2 B2 W C : (2, 4) c (5, 7) . 2 C2 Note that A = SL(5) with real form SU(5) contains B = SO(5) and C = Sp(4) as a subalgebra. 4 2 2 ∼ Since B = C we only consider the former.3 2 2 To identify the low energy eﬀective theory of this anyon model we extend our analysis to the scaling dimensions obtained from the ﬁnite size spectrum of excited states, see Table III. Clearly ⊕ our data rule out the Z parafermions since the conformal weights observed in the sector ψ ψ , 5 3 4 3 We also note that the microscopic description of the model in terms of SO(5) anyons does not go together with the symplectic structure of C . 2 ##LTLine## ##LTLine## ##LTLine##

text: This

text: allows

text: us

text: to

text: determine

text: the

text: scaling

text: dimensions

text: X

text: h

text: h¯

text: and

text: conformal

text: spins

text: s

text: h

text: h¯

text: of

text: the

text: primary

text: ﬁelds

text: present

text: in

text: the

text: CFT

text: from

text: the

text: spectrum

text: of

text: the

text: lattice

text: model

text: (n,

text: n¯

text: are

text: non-

text: negative

text: integers).

text: Solving

text: the

text: Bethe

text: equations

text: numerically

text: for

text: root

text: conﬁgurations

text: corresponding

text: to

text: a

text: particular

text: excitation

text: for

text: various

text: lattice

text: sizes

text: we

text: obtain

text: a

text: sequence

text: of

text: ﬁnite

text: size

text: estimations

text: for

text: the

text: scaling

text: dimensions

label: equation

text: L

text: L

text: L

text: L

text: Xnum(

text: E(

text: θ

text: F

text: This

text: sequence

text: is

text: then

text: extrapolated

text: to

text: obtain

text: a

text: numerical

text: approximation

text: Xext

text: to

text: the

text: scaling

text: θ

text: dimension,

text: which

text: is

text: subsequently

text: identiﬁed

text: with

text: a

text: pair

text: (h,

text: h¯)

text: of

text: conformal

text: weights.

text: Similarly,

text: the

text: central

text: charge

text: can

text: be

text: computed

text: by

text: ﬁnite

text: size

text: scaling

text: analysis

text: of

text: the

text: ground

text: state

text: energy

text: based

text: on

text: A.

text: The

text: BMW

text: model

text: at

text: θ

text: η

text: Solving

text: the

text: Bethe

text: equations

text: for

text: the

text: ground

text: state

text: conﬁguration

text: of

text: in

text: systems

text: with

text: even

text: L

text: we

text: ﬁnd

text: the

text: scaling

text: of

text: the

text: ground

text: state

text: energy

text: L

text: L−

text: L−

text: o(

text: θ=η

text: This

text: implies

text: that

text: the

text: central

text: charge

text: is

text: c

text: predicted

text: to

text: be

text: actually

text: in

text: agreement

text: with

text: the

text: ferromagnetic

text: Z

text: Fateev-Zamolodchikov

text: model.

text: This

text: central

text: charge

text: appears

text: in

text: several

text: rational

text: W

text: CFTs

text: from

text: the

text: minimal

text: series

text: of

text: Casimir-type

text: -algebras,

text: see

text: Appendix

text: Restricting

text: ourselves

text: to

text: unitary

text: ones

text: these

text: are

text: W

text: A

text: c

text: W

text: B

text: c

text: W

text: C

text: c

text: Note

text: that

text: A

text: with

text: real

text: form

text: contains

text: B

text: and

text: C

text: as

text: a

text: subalgebra.

text: Since

text: B

text: C

text: we

text: only

text: consider

text: the

text: To

text: identify

text: the

text: low

text: energy

text: eﬀective

text: theory

text: of

text: this

text: anyon

text: model

text: we

text: extend

text: our

text: analysis

text: to

text: the

text: scaling

text: dimensions

text: obtained

text: from

text: the

text: ﬁnite

text: size

text: spectrum

text: of

text: excited

text: states,

text: see

text: Table

text: III.

text: Clearly

text: our

text: data

text: rule

text: out

text: the

text: Z

text: parafermions

text: since

text: the

text: conformal

text: weights

text: observed

text: in

text: the

text: sector

text: ψ

text: ψ

text: We

text: also

text: note

text: that

text: the

text: microscopic

text: description

text: of

text: the

text: model

text: in

text: terms

text: of

text: anyons

text: does

text: not

text: go

text: together

text: with

text: the

text: symplectic

text: structure

text: of

text: C

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 28 Sector(s) P(0) Xext XCFT s (h, h¯) N N− N + 0 ⊕ L− L− ψ ψ 0 0.12500(1) 1 0.00 ( 1 , 1 ) 5( 2) + 3 3( 2) + 1 0 3 4 8 16 16 4 4 ⊕ L− L− ψ ψ π 0.62500(1) 5 0.50 ( 9 , 1 ) 5( 2) + 1 3( 2) + 1 2 3 4 2 8 16 16 4 4 ⊕ − ψ ψ π 0.62500(1) 5 0.50 ( 1 , 9 ) 3 4 2 8 16 16 L− L− ψ π 0.65000(1) 13 0.25 ( 9 , 1) 5( 2) 3( 2) 0 5 4 20 20 5 4 4 − ψ 3π 0.65000(1) 13 0.25 (1, 9 ) 5 4 20 5 20 L− L− ψ 3π 0.85000(1) 17 0.75 (4, 1 ) 5( 2) 3( 2) 2 2 4 20 5 20 4 4 − ψ π 0.85000(1) 17 0.75 ( 1 , 4) 2 4 20 20 5 ⊕ L− L− − ψ ψ 0 1.1248(1) 11 1.00 - 5( 2) + 1 3( 2) 1 4 3 4 8 4 4 ⊕ − ψ ψ 0 1.1248(1) 11 1.00 - 3 4 8 L TABLE VII. Same as Table IV but for mod 8 = 6. This insight, together with similar considerations for the other representations, is suﬃcient to set up a diﬀerential equation from which the characters of the rational CFT can be computed to arbitrary powers without additional prior knowledge of the detailed structure of the representations: the modular diﬀerential equation encodes the fact that the characters of the nine inequivalent irreps of the CFT form a nine-dimensional representation of the modular group in terms of modular − functions with asymptotic behavior ﬁxed by the numbers h c [54]. Assuming that all characters i 24 can be written as modular forms of weight 1/2 divided by the Dedekind eta-function we ﬁnd (cid:0) (cid:1) 1 (cid:0) − (cid:1) χ (q) = Θ (q) + Θ (q) Θ (q) , 0 0,5 0,4 4,4 2η(q) 1 − χ (q) = Θ (q) Θ (q) + Θ (q) , 1 0,5 0,4 4,4 2η(q) 1 χ (q) = Θ (q) , 5/4 η(q) 5,5 (5.5) 1 1 χ (q) = Θ (q) , χ (q) = Θ (q) , 1/20 η(q) 1,5 4/5 η(q) 4,5 1 1 χ (q) = Θ (q) , χ (q) = Θ (q) , 9/20 η(q) 3,5 1/5 η(q) 2,5 2 2 χ (q) = Θ (q) , χ (q) = Θ (q) . 1/16 η(q) 1,4 9/16 η(q) 3,4 (cid:88) Here we have used the Jacobi-Riemann Theta-functions (2kn+λ)2 Θλ,k(q) = q 4k . ∈Z n (cid:0) (cid:1) Note that we have introduced an explicit factor of two in the deﬁnition of χ (q) and χ (q). 1/16 9/16 − In fact, these characters as well as χ (q) = 2 q 1/24+5/4 1 + q + 2q2 + 3q3 + 5q4 + . . . should be 5/4 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Sector(s)

text: Xext

text: XCFT

text: s

text: (h,

text: h¯)

text: N

text: N−

text: N

text: L−

text: L−

text: ψ

text: ψ

text: L−

text: L−

text: ψ

text: ψ

text: π

text: ψ

text: ψ

text: π

text: L−

text: L−

text: ψ

text: π

text: ψ

text: 3π

text: L−

text: L−

text: ψ

text: 3π

text: ψ

text: π

text: L−

text: L−

text: ψ

text: ψ

text: ψ

text: ψ

text: L

text: TABLE

text: VII.

text: Same

text: as

text: Table

text: IV

text: but

text: for

text: mod

text: This

text: insight,

text: together

text: with

text: similar

text: considerations

text: for

text: the

text: other

text: representations,

text: is

text: suﬃcient

text: to

text: set

text: up

text: a

text: diﬀerential

text: equation

text: from

text: which

text: the

text: characters

text: of

text: the

text: rational

text: CFT

text: can

text: be

text: computed

text: to

text: arbitrary

text: powers

text: without

text: additional

text: prior

text: knowledge

text: of

text: the

text: detailed

text: structure

text: of

text: the

text: representations:

text: the

text: modular

text: diﬀerential

text: equation

text: encodes

text: the

text: fact

text: that

text: the

text: characters

text: of

text: the

text: nine

text: inequivalent

text: irreps

text: of

text: the

text: CFT

text: form

text: a

text: nine-dimensional

text: representation

text: of

text: the

text: modular

text: group

text: in

text: terms

text: of

text: modular

text: functions

text: with

text: asymptotic

text: behavior

text: ﬁxed

text: by

text: the

text: numbers

text: h

text: c

text: Assuming

text: that

text: all

text: characters

text: i

text: can

text: be

text: written

text: as

text: modular

text: forms

text: of

text: weight

text: divided

text: by

text: the

text: Dedekind

text: eta-function

text: we

text: ﬁnd

text: χ

text: (q)

text: Θ

text: (q)

text: Θ

text: (q)

text: Θ

text: (q)

text: χ

text: (q)

text: Θ

text: (q)

text: Θ

text: (q)

text: Θ

text: (q)

text: χ

text: (q)

text: Θ

text: (q)

text: η(q)

text: χ

text: (q)

text: Θ

text: (q)

text: χ

text: (q)

text: Θ

text: (q)

text: η(q)

text: η(q)

text: χ

text: (q)

text: Θ

text: (q)

text: χ

text: (q)

text: Θ

text: (q)

text: η(q)

text: η(q)

text: χ

text: (q)

text: Θ

text: (q)

text: χ

text: (q)

text: Θ

text: (q)

text: η(q)

text: η(q)

text: Here

text: we

text: have

text: used

text: the

text: Jacobi-Riemann

text: Theta-functions

text: Θλ,k(q)

text: q

text: ∈Z

text: n

text: Note

text: that

text: we

text: have

text: introduced

text: an

text: explicit

text: factor

text: of

text: two

text: in

text: the

text: deﬁnition

text: of

text: χ

text: (q)

text: and

text: χ

text: (q).

text: In

text: fact,

text: these

text: characters

text: as

text: well

text: as

text: χ

text: (q)

text: q

text: q

text: should

text: be

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##