György Gábor

Gulyás

Benedek Simon

Sándor Imre
email: imre@hit.bme.hu

An Efficient and Robust Social Network De-anonymization Attack

Keywords: social network, privacy, anonymity, de-anonymization

Releasing connection data from social networking services can pose a significant threat to user privacy. In our work, we consider structural social network de-anonymization attacks, which are used when a malicious party uses connections in a public or other identified network to re-identify users in an anonymized social network release that he obtained previously.

In this paper we design and evaluate a novel social deanonymization attack. In particular, we argue that the similarity function used to re-identify nodes is a key component of such attacks, and we design a novel measure tailored for social networks. We incorporate this measure in an attack called Bumblebee. We evaluate Bumblebee in depth, and show that it significantly outperforms the state-of-the-art, for example it has higher re-identification rates with high precision, robustness against noise, and also has better error control.

INTRODUCTION

The rise of social networking services has paved the way for businesses monetizing social data; however, abuses and malintents emerged as quickly as legal opportunities. In parallel, the deep integration of social networking services into everyday life provides a never seen possibility for governments to extend their spying capabilities [START_REF]What nsa's prism means for social media users[END_REF]. This asymmetry of powers between the users versus business parties and governments continuously urges the investigation of privacy issues beyond positive uses of social networks.

In this paper we consider the problem how the graph structure of a network alone can be abused to match users in different social networks, which often leads to the violation of user privacy. More specifically, we focus on large-scale reidentification attacks when two large networks are aligned together in order to de-anonymize one of them. As a result, each node in the anonymized network is either connected to a known identity in another network or not, meaning that the identity of the node is revealed (or it is de-anonymized).

There is a myriad of motivations for such attacks. For example a business party can be financially motivated in the de-anonymization of freshly bought anonymized datasets in order to update its previous records with the new data. * Corresponding author.

Meanwhile, gluing several communication networks together can be an attractive target for government agencies (e.g., email and telephone communications). Beside several sucessful attacks on social networks [START_REF] Benedek | Analysis of grasshopper, a novel social network de-anonymization algorithm[END_REF][START_REF] Ji | Structural data de-anonymization: Quantification, practice, and implications[END_REF][START_REF] Ji | Proceedings, chapter Structure Based Data De-Anonymization of Social Networks and Mobility Traces[END_REF][START_REF] Korula | An efficient reconciliation algorithm for social networks[END_REF][START_REF] Narayanan | De-anonymizing social networks[END_REF][START_REF] Nilizadeh | Community-enhanced de-anonymization of online social networks[END_REF][START_REF] Pedarsani | A bayesian method for matching two similar graphs without seeds[END_REF][START_REF] Yartseva | On the performance of percolation graph matching[END_REF], it has also been shown that location data can be de-anonymized with social networks as a background knowledge [START_REF] Ji | Proceedings, chapter Structure Based Data De-Anonymization of Social Networks and Mobility Traces[END_REF][START_REF] Srivatsa | Deanonymizing mobility traces: using social network as a side-channel[END_REF].

The algorithm proposed by Narayanan and Shmatikov in 2009 (to which we refer as Nar) was the first to achieve large-scale re-identification in social networks [START_REF] Narayanan | De-anonymizing social networks[END_REF]. Their work applied comparison of nodes based on previously discovered matching of neighboring nodes, meaning that instead of comparing each node in background knowledge to all in the anonymized graph (i.e., global comparison), their algorithm compared each node only to a smaller set of others that had been close enough to existing mappings (local comparison). This reduced computational complexity of the problem significantly, thus allowing large-scale reidentification in networks consisting of even more than a hundred thousand nodes. The authors in their main experiment re-identified 30.8% of co-existing nodes between a Twitter (224k nodes) and a Flickr (3.3m nodes) crawl with a relatively low error rate of 12.1%.

Let us now illustrate how the Nar attack works on a simple example. An adversary obtains datasets as depicted in Fig. 1, a dataset of known identities that he uses as a background knowledge (left), and an anonymized/sanitized dataset (right). The attacker's goal is to to learn political preferences by structural de-anonymization. Initially, the attacker re-identifies (or maps) some nodes that stand out globally from the dataset (the seeding phase). In our example, two top degree nodes are re-identified: Dave ↔ D and Fred ↔ F -as their degrees are outstandingly high and globally match each.

Then the attack continues by inspecting nodes related to the ones already re-identified (the propagation phase). The attacker picks a yet unidentified node in the background knowledge network. Let he first pick Harry, who has two neighbors already mapped: Dave, Fred. Nodes that could correspond to Harry in the anonymized dataset should also be neighbors of D and F, which are nodes A, B, C, E, G, H, and I. In the next step, similarity of these nodes are measured to Harry, which is calculated by dividing the number of their common mapped neighbors with their degree. This results a similarity score of 1 for nodes B, I; While the similarity metric used by Nar provides a good balance between correct and incorrect re-identification matches, it is biased towards low degree nodes. For instance, if the attacker picks Ed first, he cannot re-identify him correctly: node H would have a higher score than node E (with 2/ √ 3). Therefore we argue that selecting the right metric for comparison is a critical part of the algorithm, as it determines the performance and final limits of the attack. We propose an alternative metric, for which we show by evaluation that it significantly improves the state-of-the-art. Our main contributions are the following:

• We create a novel structural re-identification algorithm called Bumblebee, which is based on a new similarity metric specifically designed for the current re-identification task. We show that improving this critical point enhances several properties of the attack significantly. Parameters of Bumblebee allow a more fine-grained control than the Nar algorithm due to the larger score diversity.

• We evaluate the performance, robustness of Bumblebee and its sensitivity of initialization. We show that Bumblebee can reach significantly higher correct deanonymization rates while having the same or lower error rate as of Nar. In our experiments, we observe an increase of 28%-50% of correct re-identifications while error remains the same. Inversely, error rates can also be decreased close to zero. We measured error rates below 0.2% when having similar proportions of correct re-identification rates. We also show that Bumblebee is significantly more robust to noise than Nar, as it achieves large-scale correct re-identification in cases where other attacks could not rise above 1%. For seeding, we found that only 1 -2 seed nodes are enough for successful attacks, significantly smaller compared to previous works.

• We compare the performance of Bumblebee to other modern de-anonymization attacks, and show that its performance is the most outstanding compared to the state-of-the-art, even against anonymized datasets as well.

• We publish the source code of Bumblebee along our framework called Structural Anonymity Lab (SALab).

Although we used earlier versions of it in our previous works, we now release SALab as an open source framework that supports the experimental analysis of re-identification attacks in social networks. It guarantees the reproducibility of our results.

The paper is organized as follows. In Section 2, we discuss the related work, and in Section 3, we provide the methodology of our evaluation. Section 4 provides the details of the Bumblebee algorithm, and in Section 5, we evaluate our algorithm and compare it to other ones as well. Finally, in Section 6, we conclude our work.

RELATED WORK

Several attacks have followed Narayanan and Shmatikov [START_REF] Narayanan | De-anonymizing social networks[END_REF], and now we discuss the most relevant ones [START_REF] Benedek | Analysis of grasshopper, a novel social network de-anonymization algorithm[END_REF][START_REF] Ji | Structural data de-anonymization: Quantification, practice, and implications[END_REF][START_REF] Ji | Proceedings, chapter Structure Based Data De-Anonymization of Social Networks and Mobility Traces[END_REF][START_REF] Korula | An efficient reconciliation algorithm for social networks[END_REF][START_REF] Narayanan | Link prediction by de-anonymization: How we won the kaggle social network challenge[END_REF][START_REF] Nilizadeh | Community-enhanced de-anonymization of online social networks[END_REF][START_REF] Pedarsani | A bayesian method for matching two similar graphs without seeds[END_REF][START_REF] Srivatsa | Deanonymizing mobility traces: using social network as a side-channel[END_REF][START_REF] Yartseva | On the performance of percolation graph matching[END_REF]. These are heuristic approaches for solving the de-anonymization problem as finding the optimal solution is not computationally feasible [START_REF] Ji | Structural data de-anonymization: Quantification, practice, and implications[END_REF]. The attacks may also differ in many details, albeit they share some common properties. Generally, they consist of two sequentially executed phases: one for initialization (seed phase with global node comparison), and another that extends re-identification in an iterative manner (propagation phase with local node comparison). This is not a strict rule, some attacks run their propagation phase for seed generation [START_REF] Ji | Structural data de-anonymization: Quantification, practice, and implications[END_REF][START_REF] Pedarsani | A bayesian method for matching two similar graphs without seeds[END_REF], we call these selfstarting attacks. Other attacks need seeds to start, which we call seed-based attacks [5, 14, 15, 18-20, 25, 27]. Another important property of attacks is how they compare nodes. Some attacks use simple node properties for measuring node similarity [START_REF] Benedek | Analysis of grasshopper, a novel social network de-anonymization algorithm[END_REF][START_REF] Korula | An efficient reconciliation algorithm for social networks[END_REF][START_REF] Narayanan | Link prediction by de-anonymization: How we won the kaggle social network challenge[END_REF][START_REF] Narayanan | De-anonymizing social networks[END_REF][START_REF] Yartseva | On the performance of percolation graph matching[END_REF], such as Nar uses cosine similarity, while others require deeper structural properties [START_REF] Ji | Structural data de-anonymization: Quantification, practice, and implications[END_REF][START_REF] Ji | Proceedings, chapter Structure Based Data De-Anonymization of Social Networks and Mobility Traces[END_REF][START_REF] Pedarsani | A bayesian method for matching two similar graphs without seeds[END_REF][START_REF] Srivatsa | Deanonymizing mobility traces: using social network as a side-channel[END_REF], like distance vector comparison where shortest path distances are considered from already mapped nodes [START_REF] Srivatsa | Deanonymizing mobility traces: using social network as a side-channel[END_REF].

Narayanan et al. published also the first attack following [START_REF] Narayanan | De-anonymizing social networks[END_REF], that consisted of a simplified version of the original attack [START_REF] Narayanan | Link prediction by de-anonymization: How we won the kaggle social network challenge[END_REF]. Srivatsa and Hicks showed on small datasets that location traces can be re-identified by matching them to social networks [START_REF] Srivatsa | Deanonymizing mobility traces: using social network as a side-channel[END_REF], and other algorithms were proposed to this problem by Ji et al. [START_REF] Ji | Proceedings, chapter Structure Based Data De-Anonymization of Social Networks and Mobility Traces[END_REF], verified on the same datasets. Pham et al. proposed an algorithm that converts spatiotemporal data into a social network on large datasets [START_REF] Pham | Ebm: an entropy-based model to infer social strength from spatiotemporal data[END_REF]. Building upon their work, Ji et al. confirmed that location data can be efficiently re-identified with social networks [START_REF] Ji | Poster: Optimization based data de-anonymization[END_REF][START_REF] Ji | Structural data de-anonymization: Quantification, practice, and implications[END_REF]. Despite their original use, algorithms of [START_REF] Ji | Structural data de-anonymization: Quantification, practice, and implications[END_REF][START_REF] Ji | Proceedings, chapter Structure Based Data De-Anonymization of Social Networks and Mobility Traces[END_REF][START_REF] Srivatsa | Deanonymizing mobility traces: using social network as a side-channel[END_REF] can also be used on attacking regular social networks.

The algorithm designed by Nilizadeh et al. uses other attacks as a base algorithm, and it exploits the cluster-oriented structure of the networks: runs the base re-identification algorithm first on the cluster structure, then inside them [START_REF] Nilizadeh | Community-enhanced de-anonymization of online social networks[END_REF]. In their evaluation they used the Nar algorithm. Pedarsani et al. proposed the first self-starting attack that required no seeding [START_REF] Pedarsani | A bayesian method for matching two similar graphs without seeds[END_REF]. The works of Yartseva and Grossglauser [START_REF] Yartseva | On the performance of percolation graph matching[END_REF], and the paper of Korula and Lattenzi [START_REF] Korula | An efficient reconciliation algorithm for social networks[END_REF] contain simplified de-anonymization attacks in order to enable formal analysis of the algorithms. In our previous work we proposed Grasshopper [START_REF] Benedek | Analysis of grasshopper, a novel social network de-anonymization algorithm[END_REF] (also referred to as Grh), a robust attack algorithm that works with very small error rates (typically less then 1%).

The first comparative evaluation of several structural deanonymization attacks were first provided in [START_REF] Ji | Secgraph: A uniform and open-source evaluation system for graph data anonymization and de-anonymization[END_REF]. Seven algorithms in [13-15, 19, 21, 25, 27] were selected based on generality, scalability and practicality, were compared regarding robustness of background knowledge and against anonymization. Ji et al found that some algorithms were the most prominent only conditionally; they concluded that none of the evaluated algorithms could be considered as generally better than others. To the best of our knowledge, we neither know about previously published attacks that have been proven to be better in general than the Nar algorithm. Thus, we considered the Nar algorithm as the baseline attack in our work, and we included Grasshopper also, as this attack has appealing properties, like fairly high re-identification rates in general with error rates almost at zero [START_REF] Benedek | Analysis of grasshopper, a novel social network de-anonymization algorithm[END_REF]. However, we also provide comparison based on our own measurements against results published in [START_REF] Ji | Secgraph: A uniform and open-source evaluation system for graph data anonymization and de-anonymization[END_REF].

To the extent of our knowledge, the only structural reidentification framework that is similar to SALab, is Sec-Graph [START_REF] Ji | Secgraph: A uniform and open-source evaluation system for graph data anonymization and de-anonymization[END_REF]. The benefit of SecGraph is that it implements several re-identification, anonymization and utility algorithms. Unfortunately, it does not implement several important functions that are necessary for large-scale experimentation, such as synthetic dataset perturbation (e.g., as in [START_REF] Narayanan | De-anonymizing social networks[END_REF]), seed generation algorithms, and detailed evaluation of results (e.g., saving every minute detail while attacks are executed). SALab had these functions and attacks implemented already, as previous versions of it has been used in multiple works: for the analysis of the importance of seeding [START_REF] Gulyás | Measuring importance of seeding for structural de-anonymization attacks in social networks[END_REF], for measuring anonymity [START_REF] Gulyás | Measuring local topological anonymity in social networks[END_REF][START_REF] Gulyás | Using identity separation against de-anonymization of social networks[END_REF], for evaluating the Grasshopper attack [START_REF] Benedek | Analysis of grasshopper, a novel social network de-anonymization algorithm[END_REF], and for analyzing numerous settings for adopting identity separation for protecting privacy [START_REF] Gulyás | Protecting Privacy Against Structural De-anonymization Attacks in Social Networks[END_REF][START_REF] Gulyás | Hiding information in social networks from de-anonymization attacks by using identity separation[END_REF][START_REF] Gulyás | Using identity separation against de-anonymization of social networks[END_REF]. Therefore we decided to choose SALab as our main tool.

NOTATION AND METHODOLOGY

We use the following notations in our work. Given an anonymized graph Gtar = (Vtar, Etar) (target graph) to be de-anonymized by using an auxiliary data source Gsrc = (Vsrc, Esrc) (where node identities are known), let Ṽsrc ⊆ Vsrc, Ṽtar ⊆ Vtar denote the set of nodes mutually existing in both. Ground truth is represented by the mapping µG : Ṽsrc → Ṽtar denoting the relationship between coexisting nodes. Running a deterministic re-identification attack on (Gsrc, Gtar) initialized by a seed set µ0 : V µ 0 src → V µ 0 tar results in a re-identification mapping denoted as µ : V µ src → V µ tar . Nodes are denoted as vi, its set of immediate neighbors are denoted as Vi ⊆ V , and its neighbors of neighbors are denoted as V 2 i ⊆ V . In our work, we use simple measures for assessing the extent of what the attacker could learn from µ. The recall rate reflects the ratio of correct re-identifications: it is the number of correct re-identifications divided by the number of mutually existing nodes ( Ṽ ). The error rate is the proportion of incorrectly re-identified nodes compared to Ṽ ; however, as there might be erroneous mapping outside Ṽ , this leaves the possibility of the error rate to emerge above 100%. We also use precision, which is the proportion of recall divided by the mapping size (|µ|).

Data preparation and simulation parameters are key parts of methodology. We used multiple, large datasets with different characteristics in order to avoid related biases. We obtained two datasets from the SNAP collection [START_REF]Stanford network analysis platform[END_REF], namely the Slashdot network (82k nodes, 504k edges) and the Epinions network (75k nodes, 405k edges). The third dataset is a subgraph exported from the LiveJournal network crawled in 2010 by us (66k nodes, 619k edges). Datasets were obtained from real networks which assures that our measurements were being realistic.

We used the perturbation strategy proposed by Narayanan and Shmatikov [START_REF] Narayanan | De-anonymizing social networks[END_REF] to generate synthetic graph pairs for our experiments. Their method only uses deletion, thus the original graph acts as a ground truth between Gsrc, Gtar. Their algorithm makes two copies of the initial graph as Gsrc, Gtar, then performs independent deletions of nodes to achieve the desired fraction of overlap (denoted as αv), and then deletes edges independently to set the size of overlapping edges (to αe). Overlap parameters αv, αe are measured by the Jaccard similarity1 . These parameters control the level of noise in the data, therefore they are also a representation of the strength of anonymization and the quality of the adversarial background knowledge. Unless noted otherwise, we used the setting of αv = 0.5, αe = 0.75, where a significant level of uncertainty is present in the data and thus harder to attack.

The default simulation settings were set as follows. In each experiment we created two random perturbations, and run simulations once, as algorithms provided deterministic results when we used the same seed set (e.g., see top below). When seeding was random, we run the attacks multiple times. Nar and Grh both have an important parameter Θ that controls the ratio of correct and incorrect matches (greediness): the lower Θ is the less accurate mappings the algorithm will accept. As we measured fairly low error rates even for small values of Θ, we have chosen to work with Θ = 0.01 for both algorithms.

The seeding method and size have been showed to have a strong effect on the overall outcome of de-anonymization [START_REF] Gulyás | Measuring importance of seeding for structural de-anonymization attacks in social networks[END_REF]. In [START_REF] Gulyás | Measuring importance of seeding for structural de-anonymization attacks in social networks[END_REF] we provided details for various methods, and highlighted seeding methods that were top performers on large networks, regardless of the network structure, e.g., nodes with the highest degree and betweenness centrality scores. Considering these results, we applied two seeding methods. Our prime choice was selecting an initial mapping between top degree nodes (denoted as top), as this method proved to be the most effective in previous measurements in terms of run-time and smallest seed set size [START_REF] Gulyás | Measuring importance of seeding for structural de-anonymization attacks in social networks[END_REF]. It can also be used in real attacks, as a weighted graph matching technique has been proposed for top seeding in [START_REF] Narayanan | Link prediction by de-anonymization: How we won the kaggle social network challenge[END_REF]. Seed sizes were typically 50 -200 for top. In some cases, we also considered random seed selection with high degree nodes, where nodes are selected from the top 1% by degree (denoted as random.01).

THE BUMBLEBEE ATTACK

The Motivation

Biases of the similarity measure of Nar and Grh, such as we discussed in the introduction, motivated the invention of the Bumblebee attack (Blb). We now illustrate these biases and the new scoring function we propose on the source node vi ∈ Vsrc and possible mapping candidates denoted as vj ∈ Vtar. The similarity measure in Nar is a simplification of the cosine similarity [START_REF] Narayanan | De-anonymizing social networks[END_REF] as

NarSim(vi, vj) = |Vi ∩ Vj| |Vj| , (1)
where only a division with |Vi| is omitted, as this would be constant while comparing vi to any other nodes (n.b. |Vi ∩ Vj| is the number of common mapped neighbors). Unfortunately (1) shows biases towards low degree nodes when the degree of vi, vj differ significantly.

We demonstrate this on the example as shown in Fig. 2a. Here, we assume a situation where each algorithm has to make a decision, having two nodes, namely vA, vB, to find the correct mapping for. We assume a significant difference in node degrees, having deg(vA) = deg(v A ) = 100, and deg(vB) = deg(v B ) = 2, and also have 5 mappings already existing in µ of which 2 overlap. Given this situation, we calculated similarities and the resulting decisions, see it in Fig. 2b. As NarSim penalizes high degree nodes, the reidentification algorithm cannot re-identify vA.

The Grasshopper algorithm uses a similarity measure that weights mappings [START_REF] Benedek | Analysis of grasshopper, a novel social network de-anonymization algorithm[END_REF]:

GrhSim(vi, vj) = ∀(v ,v )∈{V i ∩V j } where µ(v )=v ω[v ] = ∀(v ,v )∈{V i ∩V j } where µ(v )=v |V ∩ V | |V | • |V | + 1 ( 2
)
where ω is the weight of each mapping in µ. Both ω, µ are updated at the end of every iteration. This measure is biased towards high degree nodes as the sum increases faster with a higher number of connections rather than having a smaller number of high degree adjacent nodes. Thus, GrhSim cannot discover node vB as we demonstrate this with the similarity matrix shown in Fig. 2c (all weights are equal: ∀ωi = 1).

This leads to the need of a measure which yields higher values when degree values are similar. We propose the following similarity measure to remedy the situation:

BlbSim(vi, vj) = Vi ∩ Vj • min |Vi| |Vj| , |Vj| |Vi| δ , (3)
where δ is a parameter that can be chosen freely as δ ∈ [0, 1]. This similarity measure is more balanced than the previous ones when node degrees differ, as it is symmetric and yields higher score when node degrees are closer to each other. BlbSim can correctly re-identify both vA and vB as in Fig. 2d.

Evaluation of BlbSim

Let us now evaluate if BlbSim is in fact better than Nar-Sim, and if so, under what conditions. When two nodes are compared with the discussed similarity metrics, we use the already discovered mappings in µ to glue the source and target networks together. Here, by using the mappings as additional edges, vi ∈ Vsrc and all possible candidates vj ∈ Vtar are reckoned as neighbors of neighbors in the same graph. In this setting, we assume that if nodes vi and vj correspond to each other (∃µG(vi) = vj) then vi, vj should be structurally similar (to some extent). An appropriate similarity measure S(•) should yield the highest score for S(vi, vj) than for all other possible candidates. We can also describe this with the following correct re-identification decision criteria:

S(vi, vj) > S(vi, v j ) + Θ, (4)
where vi ∈ Vsrc, vj, v j ∈ Vtar, vj = v j . The ratio between correct and false decisions depend on the value chosen for Θ ∈ [0, ∞).

Due to the way existing mappings are used, this is similar to the problem when we compare two nodes in the same graph vA, vB ∈ V . As we expected correct decisions in case of re-identification (eq. ( 4)), we expect the similarity measure S(•) to give higher score for vA to itself, then of any other node vB ∈ V \ {vA}, which is written as

S(vA, vA) > S(vA, vB) + Θ (5)
Let us call this the graph node structural comparison problem.

Theorem 1. Given the graph node structural comparison problem, having Θ = 0 and δ ≥ 1/2, BlbSim(•) leads to a higher number of correct decisions than NarSim(•).

We provide the proof for this theorem in the Appendix. While we restricted ourselves to some parameter settings in Theorem 1, later we show with experiments that Θ and δ parameters can be used together to achieve settings where the attack will exhibit interesting properties, e.g., providing high recalls or having extremely low error rates. Furthermore, as the scoring schemes output a different distribution, for BlbSim parameter Θ gives a significantly richer control of greediness (cf. in Fig. 6b).

Attack Description

We now discuss how the complete attack works based on BlbSim, for which we provide the pseudocode as in Algo. 1 and 2. After obtaining the seed set (µ0), the attack starts by iteratively calling Propagate, and it stops when no new mappings can be registered (when ∆ = 0). In each propagation step all nodes in Vsrc are checked for new mappings. Existing mappings are visited again, as this allows correction after discovering more mappings. Then we calculate the BlbSim between vsrc and all possible candidates in Score by using δ (Algo. 1 line 3). Score selects candidates by iterating unmapped neighbors of neighbors through µ (Algo. 2 lines 2-7).

If there is an outstanding candidate vc (Algo. 1 line 4), we do a reverse checking to decrease false positives. We test if we swap the graphs and invert the mapping, would vsrc be the best candidate for vc (Algo. 1 lines 8-12). If it is, we register the new mapping and indicate convergence (Algo. 1 lines 14, 15). We say that a node with maximum score in S is outstanding if its similarity score is higher than all others at least by Θ:

Ecc(S) = max(S) -max(S \ {max(S)}) σ(S) ≥ Θ. (6)
An off-the-shelf working version of this attack is available in SALab. Bumblebee inherited some parts of Nar which we found to be natural and good design choices, such as candidate selection through mappings and reverse checking to eliminate false positives. However, we use a greedy convergence criteria triggered by even the smallest changes (Algo. 1 line 15), and we redesigned the scoring function (Score) for eliminating biases. Albeit we use the same eccentricity function as Nar, due to the wider scoring diversity of Blb-Sim, this plays a more important role in Blb, and allows a more fine-grained control of the algorithm (cf. in Fig. 6b).

EVALUATION

In this section we evaluate the Bumblebee algorithm, and compare it to other attacks. Although we use multiple settings of Bumlbebee, parameters Θ and δ do remain free to choose. Best settings may depend on several factors, such as the size and structure of the dataset under analysis. We use the notation as Blb(δ) (when Θ is fixed) or as Blb(Θ, δ).

As we discussed before, we use SALab which enables analyzing various aspects of large-scale structural attacks. We also make it available at https://github.com/gaborgulyas/ salab; we hope it will contribute to further research helping to have a better understanding of structural anonymity.

Our simulations were run on a commodity computer with an Intel Xeon 3.6 GHz processor and 8 GB RAM.

Experimental Analysis of δ and Θ

First we evaluate how parameters δ and Θ influence the overall outcome. We used top seeding with 200 nodes and Θ = 0.01, meaning a greedy setting in case of Nar [START_REF] Narayanan | De-anonymizing social networks[END_REF] and Grh [START_REF] Benedek | Analysis of grasshopper, a novel social network de-anonymization algorithm[END_REF] (we provide analysis of Θ for Bumblebee later), safe enough for all algorithms to provide high recall rates [5, 3. Due to space limitations, we select results of one network for demonstration; however, until noted otherwise, we were getting similar results in the other networks as well.

Interestingly, we observed transition phases of the recall and error rates as a function of δ, which divided results into three interesting parameter subclasses for Blb. We used these classes for analyzing parameter Θ. In the first class (denoted with 1 ) we observed lower recall rates and low error. We use such a setting as δ = 0 and denote it as Blb(0). This conservative setting makes decisions only based on the number of common mappings without considering any other information. Another classes are where the recall rates plateau after increasing significantly ( 2 ). Here we selected two settings, one when recall peaked but error is relatively low, and the other when the error is also peaked [START_REF]Stanford network analysis platform[END_REF]. We observed that the recall rate usually at its highest at δ = 0.005 while error rate is still lower, thus we selected Blb(.005), and finally we selected Blb(.5) also.

We provide comparison on the effect of the Θ parameter for the LiveJournal dataset in Fig. 4. What clearly stands out from these results, that Blb could achieve the highest recall rates, while it also had higher errors for the same Θ settings compared to Nar and Grh. Furthermore, the conservative setting of Blb(0) managed to achieve higher recall than Grh with similarly low error, and in most cases higher recall as Nar, but with a lower error rate. Another interesting property of Bumblebee is that it achieved high recall rates as Nar with extremely low error, e.g., Blb(Θ = 4.0, δ = 0.5) recall = 29.91%, error = 0.15%; in other cases it achieved a significantly better trade-off between recall-error rates, as the error/recall results suggest. Comparing the recall-error results additionally shows that results provided by Grh, Blb(0) are subclasses of the results of Blb(.5). The only difference is they provide the same (recall, error) results at different values of Θ. Finally, Blb(.005) is clearly worse than Blb(.5).

From these results, we conclude that both parameters of Bumblebee enable the control of greediness in the algorithm by taking values as Θ ∈ [0, . . . , ∞), δ ∈ (0, ..., 1]. Conservative (low error) settings are typically with high Θ and low δ, greedy settings are with the opposite settings. In addition, parameters can also be used compensate each other, like as Blb(1, .5) provided high recall with low error in Fig. 4. We used these measurements to set parameters for further experiments.

Analysis of Seeding Sensitivity

The number of required seeds is an important aspect of seed-based attacks, as these need to be provided before starting propagation, or in another sense, before starting the attack. Thus, the smaller the seed size is, the better. We consider the minimum required number of seeds for which the attack is stable: observed recall and error rates only vary minimally and the recall rate reaches its maximum [START_REF] Gulyás | Measuring importance of seeding for structural de-anonymization attacks in social networks[END_REF]. We provide an example on the minimum number of seed nodes with top in Fig. 5 on Epinions dataset. Beside getting better recall and error rates than others, some Bumblebee variants managed to start with only a single seed node.

In other networks 1-2 seed nodes were enough to achieve large-scale re-identification with a higher error rate, which dropped when the number of seeds reached 5-6. We observed similar results when relaxing the seed criteria to random.01, multiple successful seeding attempts with a single random seed for Bumblebee. This means top 1% of high degree nodes, random selection from approx. a set of 200-300 nodes.

To the best of our knowledge, these results are superior to existing previous works, which reported minimum number of seeds at 16 seed nodes [START_REF] Nilizadeh | Community-enhanced de-anonymization of online social networks[END_REF], or 8 -14 seed nodes [START_REF] Benedek | Analysis of grasshopper, a novel social network de-anonymization algorithm[END_REF]. In addition, relaxed seed criteria means easier attacks: one randomly selected node from the top 1% as a seed is an easily doable task for an attacker; even with some retries or collecting a handful of seeds in order to achieve large-scale propagation.

Robustness

The quality of the background knowledge, or the overlap between Gsrc and Gtar, has a strong influence on the limits of re-identification. For example, the Grh algorithm has typically higher recall rates than Nar when the overlap is smaller [START_REF] Benedek | Analysis of grasshopper, a novel social network de-anonymization algorithm[END_REF]. In order to investigate such biases, we measured the performances of the algorithms with different perturbation settings. We note that almost all overlaps in these measurements are significantly lower than in experiments of Section 5.4.

We provide results in the Epinions network in Fig. 6a. A greedy setting of Bumblebee, Blb(.5, .5) had the highest recall rates in all cases, with an acceptable level of error except in two settings. A more conservative setting, Blb(.01, 0) provided recall rates close to Nar (and higher to Grh), but with negligible error.

In experiments with small overlap, error rates of Blb(.5, .5) were higher in case of all three networks and while staying low for Nar (as of no propagation); for Blb it reached 12% in case of Epinions. These cases were with perturbation settings αv = 0.25, αe = 0.75 and αv = 0.5, αe = 0.25. However, these are the perturbation parameters, not actual values: deleting nodes delete some edges and removing edges sometime totally disconnect nodes. Therefore we displayed the actual overlaps on the x-axis in Fig. 6a, which are measured with the Jaccard similarity [START_REF] Narayanan | De-anonymizing social networks[END_REF]. In these special cases the background knowledge and anonymized networks shared typically ≤ 10% of overlapping edges in all three networks.

In case of αv = 0.28, αe = 0.09 only Blb(.5, .5) could achieve large-scale propagation, but with high error. This can be decreased by setting parameters δ or Θ. With the latter, we could achieve recall = 12.7% with an error only at 5.1% (Θ = 1.0), or recall = 7.6%, error = 1.1% (Θ = 2.0); see more details in Fig. 6b.

We furthermore note that Fig. 6b also provides evidence that parameter Θ allows significantly more fine-grained control in Bumblebee than in the Nar algorithm. Fig. 6b is also an example how one can search the parameter space for the desired trade-off between recall and error by fixing one of the parameters.

Comparison with Other Attack Algorithms

We can now compare the performance of the Bumblebee algorithm with other modern attacks. As [START_REF] Ji | Secgraph: A uniform and open-source evaluation system for graph data anonymization and de-anonymization[END_REF] provides a recent selection and comparison of efficient structural social network de-anonymization attacks, we compare Bumblebee to these attacks under the same settings. The source code of the attacks are released with the SecGraph tool [START_REF]Secgraph: A uniform and open-source evaluation system for graph data anonymization and de-anonymization[END_REF]. Therefore, we obtained the same datasets, the Enron [START_REF]Stanford network analysis platform[END_REF] (36k nodes, 183k edges) and Facebook [START_REF]The koblenz network collection[END_REF] networks (63k nodes, 817k edges). With the sampling based perturbation method (implemented in SALab) we recreated the datasets Gsrc, Gtar as of [START_REF] Ji | Secgraph: A uniform and open-source evaluation system for graph data anonymization and de-anonymization[END_REF]: we only needed to randomly sample edges with probability s, while nodes were kept intact as much as possible. We note that this perturbation technique does notably smaller damage to the data compared to how we created synthetic datasets; for example, the lowest setting for Enron with s = 0.6 corresponds to αv = 0.77, αe = 0.42, or Enron s = 0.95 corresponds to αv = 0.97, αe = 0.90 (cf.

x-axis in Fig. 6a).

According to the results of Table 6 in [START_REF] Ji | Secgraph: A uniform and open-source evaluation system for graph data anonymization and de-anonymization[END_REF], we selected top performing attacks for comparison. For brevity, we simply provide the list of these attacks without details: percolation graph matching (later referred as YG) [START_REF] Yartseva | On the performance of percolation graph matching[END_REF], distance vector matching (DV) [START_REF] Srivatsa | Deanonymizing mobility traces: using social network as a side-channel[END_REF], reconciliation attack (KL) [START_REF] Korula | An efficient reconciliation algorithm for social networks[END_REF]. We used 50 top seeding (as in [START_REF] Ji | Secgraph: A uniform and open-source evaluation system for graph data anonymization and de-anonymization[END_REF]), and run the Nar and Blb(.1, .5) attacks from SALab. We run the three other attacks from the SecGraph implementation on the generated datasets. As both frameworks output the final the mapping µ, we could safely use this for our comparison.

We obtained results as in Fig. 7. For Nar and YG we obtained almost identical results as in [START_REF] Ji | Secgraph: A uniform and open-source evaluation system for graph data anonymization and de-anonymization[END_REF], while recall for DV Figure 7: Comparison of efficient de-anonymization algorithms. We used the same datasets, settings and code as in [START_REF] Ji | Secgraph: A uniform and open-source evaluation system for graph data anonymization and de-anonymization[END_REF], based on which we selected outstanding attacks in [START_REF] Korula | An efficient reconciliation algorithm for social networks[END_REF][START_REF] Srivatsa | Deanonymizing mobility traces: using social network as a side-channel[END_REF][START_REF] Yartseva | On the performance of percolation graph matching[END_REF] to provide a comparison with Bumblebee.

were consistently smaller, and for KL significantly higher. The latter differences can be due to configurational settings however, we tried several configurations to achieve best results for all attacks. Here, we observed that Bumblebee provided a balanced, high performance in all settings, outperforming all other attacks.

In [START_REF] Ji | Secgraph: A uniform and open-source evaluation system for graph data anonymization and de-anonymization[END_REF] only recall rates are concerned for describing the performance of de-anonymization attacks, while we found that error rates divide attacks into two strongly separated classes; we found that Nar, YG, Blb were high and DV, KL were low precision attacks. This finding puts high recalls into another perspective, as related error rates between 40-100% are unacceptably high. Therefore, while the KL attack had higher recall rates than Blb for Enron s = 0.95, with the 43.9% error rate KL had a very poor precision, unlikely to be acceptable for an attacker.

We also evaluated robustness of attacks against anonymization schemes as a comparison of Bumblebee for results in Table 8 in [START_REF] Ji | Secgraph: A uniform and open-source evaluation system for graph data anonymization and de-anonymization[END_REF] (while keeping scheme parameters identical). Again, for brevity, we only enlist the schemes we included: random edge swithcing (Switch) [START_REF] Ying | Randomizing social networks: a spectrum preserving approach[END_REF], k-degree anonymization (k-DA) [START_REF] Liu | Towards identity anonymization on graphs[END_REF], and a method providing differential privacy (DP) [START_REF] Sala | Sharing graphs using differentially private graph models[END_REF]. We left out a clustering approach due to unreasonably long runtimes [START_REF] Thompson | The union-split algorithm and cluster-based anonymization of social networks[END_REF], and a random walk based graph regeneration method [START_REF] Mittal | Preserving link privacy in social network based systems[END_REF] -against the latter we could not achieve recall rates higher than 1% with any of the algorithms.

Here, we first sampled the background knowledge network from the original datasets with probability s, and obtained the anonymized network by running the anonymization algorithms also on the original datasets (no sampling). We observed robustness of evaluated attacks as in Table 1. In case of anonymization, Blb proved to be generally the most robust attack, as it always achieved successful attacks with the high recall rates compared to others with high precision. It had error rates around 1-2%, exceptionally 5-6% only for Enron, DP = 50. The latter was exceptional as this was the only case when another attack provided higher recall than Bumblebee; however, KL provided very poor precision with error rates between 61.7%-70.2%.

These results show that Bumblebee is generally a balanced, robust, high performing attack with low error rates, outstanding of the state-of-the-art. Beside, while Bumblebee had runtimes typically between 5-10mins in each case, not all others were that fast, for example, KL had runtimes between 12-24h.

Complexity and Runtime

Runtimes of Bumblebee depend mainly on the complexity of propagation iterations and speed of convergence. The complexity of the Bumblebee propagation phase is O(dsrc • dtar • (|Vsrc| + 1)), where dsrc, dtar denotes maximum degree in each graph. The algorithm iterates over ∀v ∈ Vsrc. We assume having mapping μ when inspecting v, and the algorithm selects the neighbors-of-neighbors of v. More precisely, neighbors are ∀v ∈ V ⊆ Vsrc having |V | ≤ dsrc, and their neighbors are the neighbors of the mapped counterparts of v, the neighbors of v = μ(v ). Here V ⊆ Vtar is upper bounded as |V | ≤ dtar. This leads us to O(|Vsrc| • dsrc • dtar). We need to add the reverse checking complexity (O(dtar • dsrc)) which leads us to the given bound.

However, this does not necessarily captures the total runtime, as it significantly depends on the speed on the convergence, i.e., how fast the algorithm converges to its final result in terms of the number of new re-identifications in each propagation round [START_REF] Benedek | Analysis of grasshopper, a novel social network de-anonymization algorithm[END_REF][START_REF] Gulyás | Protecting Privacy Against Structural De-anonymization Attacks in Social Networks[END_REF]. In addition, run-times need to be handled with caution and these should be only compared when Nar and Blb achieve high re-identification rates; otherwise, significant differences could occur. For instance, the number of propagation rounds could be less for the algorithm that has lower recall as it finishes before.

In order to avoid such biases, we compared runtimes and the number of propagation rounds where both algorithm achieved very high recall rates both (see in Fig. 8a). We found that Blb(.1, .5) converges faster in a lower number of rounds compared to Nar, as its convergence profile is quite Table 1: Robustness of attacks against different anonymization schemes from [START_REF] Liu | Towards identity anonymization on graphs[END_REF][START_REF] Sala | Sharing graphs using differentially private graph models[END_REF][START_REF] Ying | Randomizing social networks: a spectrum preserving approach[END_REF]. Values are recall rates [%] (denoted as Rc) and precision [%] (Pr) of each algorithm under the given settings. Settings and parameters are intentionally replicating results of [START_REF] Ji | Secgraph: A uniform and open-source evaluation system for graph data anonymization and de-anonymization[END_REF] in order to enhance comparability of results. different (cf. Fig. 8b and8c). Blb re-identifies the majority of nodes in the first propagation round and then converges for some rounds, while Nar has a slower convergence. This is also shown by the average number of propagation rounds, which was 11.5 for Nar and 8.3 for Blb, while each round turned to be longer for Blb. The average final runtimes were t Blb = 311 secs and tNar = 263 secs, which are notable, but not dramatic differences.

CONCLUSION

In this paper, we considered structural social network deanonymization attacks, where we argued that node similarity metric plays a critical part. In fact, in order to improve that critical step, we proposed a new metric designed specifically for social networks, which we incorporated our new attack called Bumblebee.

We evaluated the new attack in different real-life networks and under multiple settings. We showed that Bumblebee outperforms the baseline attack in multiple aspects, as it is robust to noise and when attacker background knowledge is weak. We have also shown improvement in the minimum required size of seed sets, achieved high recall rates. Bumblebee allows a fine-grained control over the trade-off between yield and error; which either allows fixing error rates for reaching higher recall than other attacks, or decreasing the level of error.

We have also compared Bumblebee to the other state-ofthe-art attacks, and found that Bumblebee was highly efficient under all circumstances, even against different anonymization schemes. Reaching high recall with high accuracy in all cases, with balanced performance against noise and anonymization attempts make Bumblebee the most outstanding attack within the state-of-the-art.

APPENDIX A. PROOF FOR THEOREM 1

Proof. We expect that equation (5) will hold for Nar-Sim. Substituting equation ( 1) into (5):

|VA| |VA| > |VA ∩ VB| |VB| (7)
Similarly with (3), we get the following for BlbSim:

|VA| > |VA ∩ VB| • min |VA| |VB| , |VB| |VA| δ (8)
We can rearrange these equations to the following form:

|VA| |VA ∩ VB| > |VA| |VB| and |VA| |VA ∩ VB| > min |VA| |VB| , |VB| |VA| δ . (9)
If NarSim scores give an upper-bound to BlbSim, then BlbSim will meet the criteria in (5) for more cases. This means that BlbSim would make more correct similarity comparisons than NarSim.

We can write the upper-bound criteria as

where the left hand side is < 1, while the right hand side is > 1, thus equation [START_REF] Gulyás | Using identity separation against de-anonymization of social networks[END_REF] holds for all values of δ. Here, for δ < 1/2, due to the negative exponent the left hand side will be > 1, while for δ ≥ 1/2 the left hand side will be ≤ 1.

This means, that equation ( 10) holds for all three cases when δ ≥ 1/2, which gets us to the statement of the Theorem.

5 Figure 2 : 3 S 4 if 8 Sr 9 if 3 if 6 for 7 if ∃µ - 1 ( 10 r1

 523489367110 Figure 2: Example for demonstrating biases in the similarity measures.

Figure 3 :

 3 Figure 3: Effect of the δ parameter on results (Slashdot dataset).

Figure 4 :

 4 Figure 4: Effect of the Θ parameter for different algorithms in the LiveJournal dataset.

Figure 5 :

 5 Figure 5: Seed sizes of top and random.01 required for large-scale re-identification (Epinions dataset).

  (a) for different perturbation settings. (overlap values are as actually measured, not as set for perturbation) (b) Different Θ values used on αv = 0.28, αe = 0.09 setting.

Figure 6 :

 6 Figure 6: Robustness comparison of different algorithms (Epinions dataset); recall and error rates for different perturbation settings.

Figure 8 :

 8 Figure 8: Blb converges faster in a lower number of rounds compared to Nar.

  down to the following cases. 1. |VA| = |VB|: Here,[START_REF] Gulyás | Using identity separation against de-anonymization of social networks[END_REF] reduces to an an equality that holds for all values of δ.2. |VA| > |VB|: We will get the following inequality(|VB|) δ (|VA|) δ ≤ |VA| |VB| ,

3 .

 3 |VA| < |VB|: Similarly, we will get:

  However, for precaution, the attacker uses the same technique to check which node would be the best match (in the public dataset) If he gets Harry ← H in this case as well, the new mapping Harry ↔ H is registered.

	Known public network	Anonymized network
		A	B	C
		D	E	F
		G	H	I
		democrat	republican
	Figure 1: Datasets for the example of de-anonymization with
	an initial re-identification mapping between some nodes.
	for H.

1/ √ 2 for nodes A, C, G; 2/ √ 3 for node E; and 2/ √ 2 for node H. As node H alone has the highest score, the attacker selects Harry → H.

JaccSim(U, V ) = |U ∩V | |U ∪V | .

Acknowledgements

The authors would like to thank Amrit Kumar, Gergely Ács and Cedric Lauradoux for reviewing draft versions of this paper and for their valuable comments and discussions. Our work is based on the idea of Benedek Simon [24]. This work was carried out during the tenure of an ERCIM 'Alain Bensoussan' Fellowship Programme.


Introduction

Mathematical models of the behavior of liquid crystals (see Fig. 1), attract much attention of scientists. The mathematical models of the hydrodynamics of incompressible, homogeneous nematic liquid crystals were firstly developed in the 1960s by J. Ericksen and F. Leslie (see, for instance, [START_REF] Ericksen | Conservation laws for liquid crystals[END_REF][START_REF] Leslie | Some constitutive equations for anisotropic fluids[END_REF]).

In this paper, we consider the full Ericksen-Leslie system of equations (see, for instance, [START_REF] De Gennes | The Physics of Liquid Crystals[END_REF]). In our previous papers, we investigated plane periodic model [START_REF] Chechkin | Nematic liquid crystals. Existence and uniqueness of periodic solutions to Ericksen-Leslie equations[END_REF][START_REF] Chechkin | Existence and uniqueness theorems for two-dimensional Ericksen-Leslie system[END_REF] and plane problem in a bounded domain [START_REF] Chechkin | Existence and uniqueness theorems in two-dimensional nematodynamics. Finite speed of propagation[END_REF][START_REF] Chechkin | Existence and uniqueness theorems for two-dimensional Ericksen-Leslie system[END_REF], homogenization of micro inhomogeneous nematic liquid crystals ( [START_REF] Ratiu | Homogenization of the equations of the dynamics of nematic liquid crystals with inhomogeneous density[END_REF] for periodic, [START_REF] Chechkin | Nematodynamics and Random Homogenization[END_REF] for random) in the case of a zero molecular moment of inertia, and two-dimensional nematodynamics in the case of a non-zero molecular moment of inertia [START_REF] Chechkin | Existence and uniqueness theorems in two-dimensional nematodynamics. Finite speed of propagation[END_REF]. We study the existence and uniqueness of solutions to the following Ericksen-Leslie system

⎧ ⎨ ⎩ u -μ u = -∇ p -∂ ∂x j ∂F ∂n x j • ∇n + F div u = 0 J n -2 q n + h = G, n = 1 (1)
where summation on repeated indices is understood and

n x j := ∂ ∂x j n.
Here, u is the Eulerian, or spatial velocity vector field, n is the director field, the constant μ > 0 is the viscosity coefficient, the constant J > 0 is the moment of inertia of the molecule, F(x, t) and G(x, t) are given external forces, and the overdot ˙:

= ∂ ∂t + u • ∇ is the material derivative. The function F (n, ∇n)
is the Oseen-Zöcher-Frank free energy and is defined by

F (n, ∇n) := 1 2 K 1 (div n) 2 + K (n • curl n) 2 + n × curl n 2
where K , K 1 are real positive constants. The molecular field h is defined by

h := ∂F ∂n - ∂ ∂x j

∂F ∂n x j

The pressure p and the Lagrange multiplier 2 q are determined, respectively, by the conditions div u = 0 and n = 1. In this case, the ith component of the molecular field has the expression

h i = (K -K 1 )n k x k x i -Kn i x k x k + q n i
where q is a scalar function depending on n and its derivatives. Define the linear differential operator L by

Lv := (K -K 1 )∇(div v) -K v (2)
Given the Ericksen-Leslie system (1), define the new vector field (first introduced in [START_REF] Gay-Balmaz | The geometric structure of complex fluids[END_REF])

ν := n × ṅ ∈ F (D, R 3 )
With all these hypotheses and notations, system (1) becomes

u -μ u = -∇ p + (Ln • ∇n) + F, div u = 0 ( 3 ) J ν = Ln × n + n × G (4) ṅ = ν × n (5)
with unknowns u, ν, n. Thus, the Ericksen-Leslie system (1) implies the new first-order system (3)- [START_REF] Chechkin | Existence and uniqueness theorems for two-dimensional Ericksen-Leslie system[END_REF].

Conversely, if the initial conditions of the first order system (3)-( 5) satisfy the identities n(x, 0) = 1, n(x, 0) ⊥ ν(x, 0) at time t = 0, then for any t > 0 we have

n ≡ 1, ν = n × ṅ, 2q = n • h -J ν 2
and (3)-( 5) turns into [START_REF] Ericksen | Conservation laws for liquid crystals[END_REF]. Thus, under these hypotheses on the initial conditions, the first-order system (3), ( 4), ( 5) is equivalent to the original Ericksen-Leslie system (1) (as was first noticed in [START_REF] Gay-Balmaz | The geometric structure of complex fluids[END_REF]).

The preceding papers (see [START_REF] Lin | Nonlinear theory of defects in nematic liquid crystal: phase transition and flow phenomena[END_REF][START_REF] Lin | Nonparabolic dissipative system modeling the flow of liquid crystals[END_REF][START_REF] Shkoller | Well-posedness and global attractors for liquid crystals on Riemannian manifolds[END_REF][START_REF] Hong | Global existence of solutions of the simplified Ericksen-Leslie system in dimension two[END_REF][START_REF] Lin | Liquid crystal flows in two dimensions[END_REF][START_REF] Huang | Regularity and existence of global solutions to the Ericksen-Leslie system in R 2[END_REF][START_REF] Wu | On the general Ericksen-Leslie system: Parodi's relation, well-posedness and stability[END_REF][START_REF] Dai | Existence of regular solutions to the full liquid crystal system[END_REF][START_REF] Huang | Strong solutions of the compressible nematic liquid crystal flow[END_REF] and [START_REF] Wang | Well-posedness for the heat flow of harmonic maps and the liquid crystal flow with rough initial data[END_REF]) are mostly concerned with the case J = 0.

In this article, we focus on the system (3)-( 5) with J = 0 and announce the existence and uniqueness of solutions for 3-dimensional periodic media (Theorem 2.2) as well as for the problem in a bounded domain with Dirichlet (Theorem 3.2) and Neumann-type (Theorem 4.2) boundary conditions, in appropriate natural spaces. The uniqueness theorem holds under weaker conditions than the existence theorem, i.e. the spaces in the uniqueness theorem are bigger. We also give a result on the finite speed of propagation of the director field disturbance in such media (Theorem 3.3, Corollary 3.4).

Solutions in a periodic domain

Let Q T := (0, T ) × T, where T = R 3 /Z 3 is the 3-dimensional flat torus. We study the system (3)-( 5) in

Q T with initial conditions u(0, x) = u 0 , ν(0, x) = ν 0 , n(0, x) = n 0 (6)
Here u, ν, n are unknown vector fields, p is an unknown scalar function, and J > 0, K i > 0, μ > 0 are given constants.

Throughout the paper we use the following notations:

-ḟ := ∂ f ∂t + u • ∇ f = f t + u j f x j is the material time derivative of f ; -a bold letter b denotes a 3-dimensional vector b = (b 1 , b 2 , b 3
), or a vector field with values in R 3 ; -a standard summation convention is used on repeated indices, independent of their position, e.g.,

a i b i := i a i b i ; -L 2 (T) := v : T → R 3 | v 2 2 := T v 2 dx < ∞ ; -(u, v) := T u • v dx is the inner product in L 2 (T); -W m 2 (T) is the Sobolev space of functions on T having m distributional derivatives in L 2 (T); -for any v ∈ W m 2 (T), m ∈ N, define D m v 2 2 := i 1 +i 2 +i 3 =m ∂ m v ∂x i 1 1 ∂x i 2 2 ∂x i 3 3 2 2 -Sol(T) := {v : T → R 3 | v ∈ C ∞ (T), div v = 0}; -Sol(Q T ) := {v ∈ C ∞ (Q T ) | v(t, •) ∈ Sol(T), ∀t ∈ (0, T )}; -Sol 2 (T) is the closure of Sol(T) in the norm L 2 (T); -Sol m 2 (T) is the closure of Sol(T) in the norm W m 2 (T). Definition 2.1. A quadruple (u, ν, n, ∇ p) is a strong solution to problem (3)-(6) in the domain Q T if (i) u is a time-dependent vector field in L 2 ((0, T ); Sol 3 2 (T)), u t ∈ L 2 (Q T ); (ii) ν is a vector field in L ∞ ((0, T ); W 2 2 (T)), ν t ∈ L ∞ ((0, T ); L 2 (T)); (iii) n is a vector field in L ∞ ((0, T ); W 3 2 (T)), n t ∈ L ∞ ((0, T ); W 1 2 (T)); (iv) ∇ p ∈ L 2 (Q T ); (v) u, n, ν satisfy the initial conditions (6), i.e. (u, n, ν) (u 0 , n 0 , ν 0 ) in L 2 (T) as t → 0;
(vi) Eqs. ( 3)-( 5) hold almost everywhere.

The following assertion is valid.

Theorem 2.2. Suppose u 0 ∈ Sol 2 2 (T), ν 0 ∈ W 2 2 (T), n 0 ∈ W 3 2 (T), and F ∈ L 2 ((0, T ); W 1 2 (T)), G ∈ L 1 ((0, T ); W 2 2 (T)).
Then there is a T > 0 such that the solution to problem (3)-( 5), (6) (as given in Definition 2.1) does exist. Let

(u 1 , ν 1 , n 1 , p 1 ) and (u 2 , ν 2 , n 2 , p 2 ) be solutions to problem (3)-(6) in the domain Q T . Then, for some 0 < T 0 ≤ T (u 2 , ν 2 , n 2 , ∇ p 2 ) = (u 1 , ν 1 , n 1 , ∇ p 1 ) almost everywhere in Q T 0 .
The proof is based on Galerkin-type approximations.

Solutions with Dirichlet-type boundary conditions

Let be a bounded domain in R 3 and consider nematic liquid crystal flow in the cylinder × R. We study Eqs. ( 3)-( 5) in the domain (0, T ) × with initial conditions [START_REF] Chechkin | Existence and uniqueness theorems in two-dimensional nematodynamics. Finite speed of propagation[END_REF] and additional boundary conditions u ∂ = 0, n -n 1 ∂ = 0, ν| ∂ = 0 for any t > 0 [START_REF] Ratiu | Homogenization of the equations of the dynamics of nematic liquid crystals with inhomogeneous density[END_REF] where n 1 is a given vector field on .

Condition u ∂ = 0 means that the domain has impenetrable boundary and that the fluid moves without slipping; nn 1 ∂ = 0 describes the director position at the boundary. The third condition comes from the original Ericksen-Leslie system and means that ṅ = 0 at the boundary.

In this section, we let Q T := (0, T ) × and introduce the function spaces

• Sol ( ) := {v : → R 3 | v has compact support, div v = 0} • Sol (Q T ) := {v ∈ C ∞ (Q T ) | v(t, •) ∈ • Sol ( ), ∀t} • Sol m 2 ( ) is the closure of • Sol ( ) in the norm W m 2 ( )
The definition of a solution to the Ericksen-Leslie equations is the natural modification for the case of a bounded domain with boundary of the one given in Definition 2.1.

Definition 3.1. The quadruple (u, ν, n, ∇ p) is a strong solution to problem (3)-( 6), [START_REF] Ratiu | Homogenization of the equations of the dynamics of nematic liquid crystals with inhomogeneous density[END_REF]

in the domain Q T if -u is a vector field in L 2 ((0, T ); • Sol 1 2 ( )) ∩ L 2 ((0, T ); W 3 2 ( )), u t ∈ L 2 (Q T ); -ν is a vector field in L ∞ ((0, T ); • W 1 2 ( )) ∩ L ∞ ((0, T ); W 2 2 ( )), ν t ∈ L ∞ ((0, T ); L 2 ( )); -n -n 1 is a vector field in L ∞ ((0, T ); • W 1 2 ( )) ∩ L ∞ ((0, T ); W 3 2 ( )),
where n 1 is a given constant vector field, and 3)-( 5) hold almost everywhere.

n t ∈ L ∞ ((0, T ); W 1 2 ( )); -∇ p ∈ L 2 (Q T ); -u, n, ν satisfy initial conditions (6), i.e. (u, n, ν) (u 0 , n 0 , ν 0 ) in L 2 ( ); -Eqs. (
The following result is proved in the same way as Theorem 2.2, with natural modifications. Theorem 3.2. Assume that for all x ∈ ∂ the boundary is the graph of a C 2 -function in some neighborhood of x. Let n 1 = const,

n 0 ∈ • W 3 2 ( ), ν 0 ∈ W 2 2 ( ), u 0 ∈ • Sol 1 2 ( ) ∩ W 2
2 ( ), u 0 ∂ = 0, and assume that, for some d > 0, we have

n 0 (x) = const, ν 0 (x) = 0 if dist(x, ∂ ) < d Assume also that F ∈ L 2 ((0, T ); W 1 2 ( )), G ∈ L 1 ((0, T ); W 2 2 (
)), G equal to zero in a neighborhood of ∂ . Then problem (3)-( 6), ( 7) has a unique solution in Q T for some T > 0.

Instead of (3)-( 5), we consider the system [START_REF] Lin | Nonlinear theory of defects in nematic liquid crystal: phase transition and flow phenomena[END_REF] where (x) ∈ C ∞ ( ) is a given smooth non-negative function with compact support.

u -μ u = -∇ p + (Ln • ∇n) , div u = 0 ( 8 ) J (ν t + u i ν x i ) = (Ln × n) (9) n t + u i n x i = (ν × n)
Theorem 3.3. Fix u ∈ L 2 ((0, T ); • Sol 1 2 ( )) ∩ L 2 ((0, T ); W 2 2 ( )) and ∈ C ∞ ( ) with compact support, 0 ≤ ≤ 1. Consider Eqs. ( 9)
, [START_REF] Lin | Nonlinear theory of defects in nematic liquid crystal: phase transition and flow phenomena[END_REF] for this given vector field u.

Suppose, in addition, that for some 1 < α ≤ ∞ and for all i, j, there are constants m > 0, M > 0 such that the vector field u satisfies esssup

x |u i x j (x, t)| L α (0,T ) ≤ M and u(x, t) ≤ m, ∀(x, t) ∈ Q T
Assume also that the initial conditions n 0 and ν 0 of (9), [START_REF] Lin | Nonlinear theory of defects in nematic liquid crystal: phase transition and flow phenomena[END_REF], with this given vector field u, are such that ∇n 0 and ν 0 vanish for xx 0 < r. Then there exist constants m , t 0 > 0 such that ∇n and ν are equal to zero for all (x, t) satisfying xx 0 < rm t, t < t 0 Remark 1. A similar result, with identical proof, holds in a periodic domain. In this case, we assume u ∈ L 2 ((0, T ); Sol 1 2 (T)) ∩ L 2 ((0, T ); W 2 2 (T)) and take ≡ 1.

Corollary 3.4. Consider a solution (u, ν, n, p) of the problem (3)-( 5), [START_REF] Chechkin | Existence and uniqueness theorems in two-dimensional nematodynamics. Finite speed of propagation[END_REF] in the periodic domain, as given in Definition 2.1.

Assume also that the initial conditions n 0 and ν 0 are such that ∇n 0 and ν 0 vanish for xx 0 < r. Then there exist constants m , t 0 > 0 such that ∇n and ν are equal to zero for all (x, t) satisfying xx 0 < rm t, t < t 0 If (u, ν, n, p) is the solution to problem (3)-( 6), [START_REF] Ratiu | Homogenization of the equations of the dynamics of nematic liquid crystals with inhomogeneous density[END_REF] in a bounded domain, we need to assume, in addition, that ν, ∇n vanish in some neighborhood of the boundary ∂ .

Solutions with Neumann-type boundary conditions

The problem considered in Section 3 has an important drawback: the director vector field is assumed to be constant near the boundary. As shown below, this condition can be neglected if we change the boundary conditions. Suppose that K 1 = K = K and consider the domain as being a cuboid, i.e.

= 3 i=1 (a i , b i ), where -∞ < a i < b i < ∞.
The equations of motion are (3)-( 5) with initial conditions ( 6), but instead of the boundary conditions ( 7), we require

u • N (0,T )×∂ = 0 and u i x j τ i N j (0,T )×∂ = 0 ∀τ ⊥ N = 0 (11)
The boundary condition on the director field n and the variable ν are

n x i N i (0,T )×∂ = 0 and ν x i N i = 0 (12)
Definition 4.1. The quadruple (u, ν, n, ∇ p) is a strong solution to problem (3)-( 6), ( 11), [START_REF] Shkoller | Well-posedness and global attractors for liquid crystals on Riemannian manifolds[END_REF] in the domain Q T if

• u is a vector field in L 2 ((0, T ); Sol 1 2 ( )) ∩ L 2 ((0, T );

W 3 2 ( )), u t ∈ L 2 (Q T );
• ν is a vector field in L ∞ ((0, T ); W 2 2 ( )), ν t ∈ L ∞ ((0, T ); L 2 ( ));

• n is a vector field in L ∞ ((0, T ); W 3 2 ( )), where n 1 is a given constant vector field, and n t ∈ L ∞ ((0, T ); W 1 2 ( ));

• ∇p ∈ L 2 (Q T );
• u, n, ν satisfy the initial conditions (6), i.e. (u, n, ν) (u 0 , n 0 , ν 0 ) in L 2 ( );

• Eqs. ( 3)-( 5) and boundary conditions [START_REF] Lin | Nonparabolic dissipative system modeling the flow of liquid crystals[END_REF], [START_REF] Shkoller | Well-posedness and global attractors for liquid crystals on Riemannian manifolds[END_REF] hold almost everywhere. 6), [START_REF] Lin | Nonparabolic dissipative system modeling the flow of liquid crystals[END_REF], [START_REF] Shkoller | Well-posedness and global attractors for liquid crystals on Riemannian manifolds[END_REF] has a unique solution in Q T for some T > 0.

Fig. 1 .

 1 Fig. 1. The structure of horizontal flow of smectic (left), nematic calamitic and nematic discotic (center), cholesteric (right) liquid crystals.

Theorem 4 . 2 . 2 2 ( ), u 0 ∈ Sol 1 2

 4221 Assume that is the cuboid3 i=1 (a i , b i ) with -∞ < a i < b i < ∞. Let n 0 ∈ W 3 2 ( ), ∂n ∂ N ∂ = 0, ν 0 ∈ W ( ) ∩ W 2 2 ( ), u 3 0 | ∂ = 0. Suppose also that F ∈ L 2 ((0, T ); W 1 2 ( )), G ∈ L 1 ((0, T ); W 2 2 ( )), and G i N i | ∂ = 0. Then problem (3)-(


P Fraundorf

Melanie Lipp

Molar standards & information units in the 'new-SI'

In a 2015 paper, Mohr and Phillips point out practical ambiguities associated with the treatment of dimensionless units in the SI, with an eye toward helping scientists to address these in the future. In particular the two fundamental constants "related to counting", namely Avogadro's number NA and Boltzmann's constant kB, in the proposed new SI will serve primarily as scaling relations between dimensionless quantities. We show here that the role of molar heat capacity as a multiplicity exponent gives to the numerical value chosen for kB a natural connection to information units, like bits. At the same time, the promise of graphene (e.g. in nanotube form) as a portable molar and mass standard (thanks to its small intersheet-bonding mass deficit) suggests a natural connection between the numerical value chosen for NA and well-defined graphene structures, including a particular graphite arm-chair hex-prism. CONTENTS I. Introduction 1 II. Avogadro and size scales 1 III. Boltzmann and information units 2 IV. Discussion

I. INTRODUCTION

The recent paper by Mohr and Phillips 1 raises important issues about the explicit specification of "dimensionless" units, and has helped to broaden the discussion of strategies [START_REF] Quincey | Comment on dimensionless units in the SI[END_REF][START_REF] Leonard | Comment on 'Dimensionless units in the SI[END_REF] for considering such units in the upcoming revision of the international system of units [START_REF]General Conference on Weights and Measures (CGPM) at its 25th meeting[END_REF] . For example, measures of spatial frequency (like wavenumber, reciprocal lattice vector magnitude, etc.) implicitly vary with discipline 5 (e.g. as 2π/λ or 1/d hkl ) when (as is often done) they are listed only as "reciprocal distance". The explicit specification of angle units (like radians or cycles) would remove this ambiguity, and make the conventions cross-consistent as well.

This note focuses instead on the two fundamental constants that involve counting 1 , and on the possiblity that along with "dimensionless" units for angles and counting the proposed new SI might also want to consider dimensionless units for information. Following Taylor 6 , one might define unit [A] in terms of an implicitlyphysical, as e.g. in Taylor's equation 3b, "invariantquantity" A divided by a numerical reference constant {A} [A] that we are free to choose in context of both existing practice and future needs. Here we make the case that Avogadro's number N A and Boltzmann's constant k B don't have physical invariants associated with them, but that they are instead scale-factors which connect physically-dimensionless size scales (N A ) or information units (k B ). As a result it might make sense to choose the unit-defining numerical constant for N A to a physical structure with potential for replicating standards downstream, and to link the numerical constant for k B to an information-unit convention. Specific possibilities are suggested as well.

II. AVOGADRO AND SIZE SCALES

In the proposed new SI, the second [s] may be defined in terms of the ground-state hyperfine splitting transition-frequency of Cs-133, the meter [m] then in terms of the lightspeed constant, the kilogram [kg] and joule [J] then in terms of Planck's constant, the coulomb [C] and ampere [A] in terms of the fundamental charge, and the lumen [lm] and candela [cd] in terms of the luminous/radiant intensity-ratio for 540[THz] light.

The new SI may also decouple the definition of Avogadro's number from the number of Daltons (defined not by the SI e.g. as one twelfth the mass of an isolated C-12 atom) per gram [START_REF] Leonard | Why the dalton should be redefined exactly in terms of the kilogram[END_REF] . This is perhaps reasonable given the fact that, when molecular binding energies are considered, mass is not simply proportional to the number of atoms in an object. Hence Avogadro's number N A would not be linked to an experimental invariant, like the number of isolated C-12 atoms needed to make up a kilogram of mass. Without a physical invariant, this makes Avogadro's number a scale-factor for the dimensionless quantity "number of entities' in moving from the size-scale of atoms and molecules to the human-specific "macroscopic" size scale of the laboratory.

Hence the mole [mol] may be defined by picking any number consistent with prior practice, or by "in additon" asking that the numeric value of N A be associated with a physical object for which precise molar standards (with a specified number of atoms/molecules) may be possible to generate in the days ahead. One such standard might be a well-defined 3-dimensional graphite structure. This is because graphite is quite stable (in the absence of hot oxygen & molten iron), and is made of graphene sheets which might be generated e.g. with well-defined chirality by future nanotube generators to create portable molar standards. These in turn, thanks to the weak binding between graphene sheets, could also serve as relatively precise mass standards independent of the layeringconfiguration of the graphene sheets themselves.

For example, imagine that Avogadro's number N A was defined as the number of atoms in an arm-chair graphite hex-prism with m hexagonal graphene sheets each with m atoms on a side, using:

entities mol ≡ N A 6.022 141... × 10 23 ≃ N A 3m 2 + 9m 3 /2 . (1)
We specifically propose 8 using m = 51, 150, 060 carbon atoms along the sides and height of an armchair-graphite hex-prism, as a value which perhaps provides the closest match to the experimental value at present.

III. BOLTZMANN AND INFORMATION UNITS

The statistical approach to thermal physics, pioneered by Ed Jaynes 9,10 in the 1950's to include the informationtheory connection between Gibb's work and statistical inference [START_REF] Gibbs | The collected works of J. W. Gibbs[END_REF] , in the second half of the 20th century has pretty much found its way into all senior undergraduate thermal physics texts 12-15 even if it is not familiar across all disciplines. It includes the recognition that reciprocaltemperature has natural (as distinct from historical) units as energy's uncertainty slope (1/T = dS/dE), which stem from its role as a Lagrange multiplier in the uncertainty maximization for "taking the best guess" about where energy (when shared randomly) will go.

More recently, a strong connection between the 2nd law of thermodynamics, these uncertainty measures, and subsystem correlations in general has been established. For example, Seth Lloyd has discussed the role of the multi-moment correlation-measure mutual information in the context of quantum computing [START_REF] Lloyd | Use of mutual information to decrease entropy: Implications for the second law of thermodynamics[END_REF] . This is a special case (namely that for an uncorrelated reference probability set) of an even more general correlation measure called Kullback-Liebler divergence [START_REF] Kullback | On information and sufficiency[END_REF] or relative/cross-entropy [START_REF] Gregory | Bayesian logical data analysis for the physical sciences: A comparative approach with Mathematica support[END_REF] , which e.g. is behind engineering measures (like "exergy") for available work in a given setting [START_REF] Tribus | Energy and information[END_REF][START_REF] Szargut | Exergy analysis of thermal, chemical, and metallurgical processes[END_REF] . Work on applying KL-divergence, in turn, to layered complex systems 21 (e.g. behind life's dependence on thermodynamic availability) as well as to model selection (with separate converging threads in both the behavioral [START_REF] Burnham | Model selection and multimodel inference: A practical information-theoretic approach[END_REF] and physical 18 sciences) are active areas of applied research.

Stepping back to the mathematics of statistical inference [START_REF] Jaynes | Probability theory: The logic of science[END_REF] , just as cycle and angle "units" arise when we mark a unitless interval-fraction (e.g. in units of the repeat-period) along the path of a periodic function, so information "units" of base-b arise when we take the log to the base-b of a unitless reciprocal-probability. Hence the surprisal 24 s ≡ k ln[1/p] ≥ 0 associated with any

probability 0 ≤ p ≤ 1 has "dimensionless" units of [bits] if k = 1/ ln 2, [nats] if k = 1, or [J/K] if k = k B in units of [J/K]
is taken as dimensionless. Uncertainties and entropies are generally defined as "average surprisals", while KL-divergence based measures of (delocalized) correlation between subsystems, as well as of available information on deviations from ambient, define a kind of "netsurprisal" that may also be expressed in energy units (e.g. as available work) if multiplied by ambient temperature in [K].

It is natural in this context to ask "What specific correlations are being linked to the 2nd law?". The answer might be "correlations between the state of any two separate physical systems or subsystems". A classic example [START_REF] Szilard | Uber die entropieverminderung in einem thermodynamischen system bei eingriffen intelligenter wesen[END_REF][START_REF] Bennett | Demons, engines and the second law[END_REF][START_REF] Bennett | Chain letters and evolutionary histories[END_REF][START_REF] Jonne | Experimental realization of a Szilard engine with a single electron[END_REF] is the Szilard "vacuum-pump memory", which in simplest form (Fig. 1) is a two-chamber structure with a removable partition and one gas atom bouncing around inside. Imagine that there is no record in the outside world as to which side the atom is on. By using e.g. a piston to reversibly push the "gas" into say the left chamber we thermalize (at constant T) an available

work of W = (k B T )[J/nat] ln(V o /V )[nat] = k B T ln 2[J],
but we also lessen our total uncertainty about the state of the "structure plus outside world" by ∆S

/k B = Q[J]/(k B T )[J/nat] = ln 2[nat] = 1[
bit] of mutual information (correlation between our idea of which side the atom is on, and the position of the atom itself). Here as usual W is work done to compress and Q is heat lost to hold T constant, both in [J], and S is the entropy of our 1-atom gas in [J/K]. The second law of course allows us to irreversibly forget which side we put it on, but makes it less likely that we'll unforget something we never knew.

In this context, therefore, the kelvin [K] may be defined by expressing the thermodynamic information unit [J/K] for measuring subsystem correlations, expressed in terms of everyday measures of energy and temperature (the reciprocal of energy's uncertainty-slope dS/dE), as a certain number of [bits] (the smallest standard unit of information) via the relationship which connects e.g. molar heat capacity [START_REF] Fraundorf | Heat capacity in bits[END_REF] This integer may be selected to match the current value of Boltzmann's constant to any precision, or as a binary multiple times a prime number. A 6-figure match is e.g. provided by k B as 1/(2 61 45317 ln 2)[J/nat K]. Unfortunately the large size of that prime number (45,317) limits the mnemonic value of this choice, over e.g. simple truncation of a decimal.

IV. DISCUSSION

In this comment we reinforce the case made by Mohr and Phillips 1 that dimensionless units are an important element of future work with fundamental constants. We suggest adding "standards generation" into the choice of a numerical constant for Avodagro's number, and adding information units into the discussion of a specific value for Boltzmann's constant. One possible example of each is also provided.

FIG. 1 .

 1 FIG.1. Single-atom isothermal-setting process schematic.

  in [J/K] to the number of molecular degrees-freedom in a gas: × 10 -23 ≃ nk B ln 2(2) where k B is Boltzmann's constant and n ≃ 1.0449378 × 10 23 is an integer, so that 1[J/K] is about 13.0617[ZB] ≃ 11.0637[ZiB], where [ZiB] is a possible binary-multiple unit symbol for 1[zebibyte] ≡ 2 73 [bits].

	Joule nat Kelvin	≡	k B 1.380 648...