Jorge C Valverde-Rebaza

Mathieu Roche

Pascal Poncelet

Alneu De

Andrade Lopes

The role of location and social strength for friendship prediction in location-based social networks

Keywords: Location-based social networks, Link prediction, Friendship recommendation, Human mobility, User behavior

Recent advances in data mining and machine learning techniques are focused on exploiting location data. There, combined with the increased availability of location-acquisition technology, has encouraged social networking services to offer to their users different ways to share their location information. These social networks, called location-based social networks (LBSNs), have attracted millions of users and the attention of the research community. One fundamental task in the LBSN context is the friendship prediction due to its role in different applications such as recommendation systems. In the literature exists a variety of friendship prediction methods for LBSNs, but most of them give more importance to the location information of users and disregard the strength of relationships existing between these users. The contributions of this article are threefold, we: 1) carried out a comprehensive survey of methods for friendship prediction in LBSNs and proposed a taxonomy to organize the existing methods; 2) put forward a proposal of five new methods addressing gaps identified in our survey while striving to find a balance between optimizing computational resources and improving the predictive power; and 3) used a comprehensive evaluation to quantify the prediction abilities of ten current methods and our five proposals and selected the top-5 friendship prediction methods for LBSNs. We thus present a general panorama of friendship prediction task in the LBSN domain with balanced depth so as to facilitate research and real-world application design regarding this important issue.

Introduction

In the real world, many social, biological, and information systems can be naturally described as complex networks in which nodes denote entities (individuals or organizations) and links represent different interactions between these entities. A social network is a complex network in which nodes represent people or other entities in a social context, whilst links represent any type of relationship among them, like friendship, kinship, collaboration or others [START_REF] Barabási | Network Science[END_REF].

With the growing use of Internet and mobile devices, different web platforms such as Facebook, Twitter and Foursquare implement social network environments aimed at providing different services to facilitate the connection between individuals with similar interests and behaviors. These platforms, also called as online social networks (OSNs), have become part of the daily life of millions of people around the world who constantly maintain and create new social relationships [START_REF] Zheng | Computing with Spatial Trajectories[END_REF][START_REF] Yu | Friend recommendation with content spread enhancement in social networks[END_REF]. OSNs providing location-based services for users to check-in in a physical place are called location-based social networks (LBSNs) [START_REF] Cho | Friendship and mobility: User movement in location-based social networks[END_REF][START_REF] Zhu | Understanding the adoption of location-based recommendation agents among active users of social networking sites[END_REF][START_REF] Valverde-Rebaza | Exploiting social and mobility patterns for friendship prediction in location-based social networks[END_REF][START_REF] Ozdikis | Evidential estimation of event locations in microblogs using the dempstershafer theory[END_REF].

One fundamental problem in social network analysis is link prediction, which aims to estimate the likelihood of the existence of a future or missing link between two disconnected nodes based on the observed network information [START_REF] Liben-Nowell | The link-prediction problem for social networks[END_REF][START_REF] Lü | Link prediction in complex networks: A survey[END_REF][START_REF] Martínez | A survey of link prediction in complex networks[END_REF][START_REF] Wu | A balanced modularity maximization link prediction model in social networks[END_REF]. In the case of LBSNs, the link prediction problem should be dealt with by considering the different kinds of links [START_REF] Bao | Recommendations in locationbased social networks: A survey[END_REF][START_REF] Zheng | Computing with Spatial Trajectories[END_REF][START_REF] Li | Mining user similarity based on location history[END_REF]. Therefore, it is called friendship prediction when the objective is to predict social links, i.e. links connecting users, and location prediction when the focus is to predict userlocation links, i.e. links connecting users with places [START_REF] Valverde-Rebaza | Exploiting social and mobility patterns for friendship prediction in location-based social networks[END_REF][START_REF] Wang | A recommender system research based on location-based social networks[END_REF][START_REF] Pálovics | Locationaware online learning for top-k recommendation[END_REF].

Since location information is a natural source in LBSNs, several techniques have been proposed to deal with the location prediction problem [START_REF] Bao | Recommendations in locationbased social networks: A survey[END_REF][START_REF] Zheng | Computing with Spatial Trajectories[END_REF]. However, to the best of our knowledge no studies have analyzed the performance of friendship prediction methods in the LBSN domain.

In this paper, we review existing friendship prediction methods in the LBSN domain. Moreover, we organize the reviewed methods according to the different information sources used to make their predictions. We also analyze the different gaps between these methods and then propose five new friendship prediction methods which more efficiently explore the combination of the different identified information sources. Finally, we perform extensive experiments on well-known LBSNs and analyze the performance of all the friendship prediction methods studied not only in terms of prediction accuracy, but also regarding the quality of the correctly predicted links. Our experimental results highlight the most suitable friendship prediction methods to be used when real-world factors are considered.

The remainder of this paper is organized as follows. Section 2 briefly describes the formal definition of an LBSN. Section 3 formally explains the link prediction problem and how it is dealt with in the LBSN domain. This section also presents a survey of different friendship prediction methods from the literature. Section 4 presents our proposals with a detailed explanation on how they exploit different information sources to improve the friendship prediction accuracy. Section 5 shows experimental results obtained by comparing the efficiency of existing friendship prediction methods against our proposals. Finally, Section 6 closes with a summary of our main contributions and final remarks.

Location-Based Social Networks

A location-based social network (LBSN), also referred to as geographic social network or geo-social network, is formally defined as a specific type of social networking platform in which geographical services complement traditional social networks. This additional information enables new social dynamics, including those derived from visits of users to the same or similar locations, in addition to knowledge of common interests, activities and behaviors inferred from the set of places visited by a person and the location-tagged data generated during these visits [START_REF] Zheng | Computing with Spatial Trajectories[END_REF][START_REF] Allamanis | Evolution of a location-based online social network: Analysis and models[END_REF][START_REF] Bao | Recommendations in locationbased social networks: A survey[END_REF][START_REF] Valverde-Rebaza | Exploiting social and mobility patterns for friendship prediction in location-based social networks[END_REF][START_REF] Narayanan | A study and analysis of recommendation systems for location-based social network (LBSN) with big data[END_REF].

Formally, we represent an LBSN as an undirected network G(V, E, L, Φ), where V is the set of users, E is the set of edges representing social links among users, L is the set of different places visited by all users, and Φ is the set of check-ins representing connections between users and places. This representation reflects the presence of two types of nodes: users and locations, and two kinds of links: user-user (social links) and user-location (check-ins), which is an indicator of the heterogeneity of LBSNs [START_REF] Zheng | Computing with Spatial Trajectories[END_REF][START_REF] Mengshoel | Will we connect again? machine learning for link prediction in mobile social networks[END_REF][START_REF] Zhang | Transferring heterogeneous links across location-based social networks[END_REF] Multiple links and self-connections are not allowed in the set E of social links. On the other hand, only self-connections are not allowed in the set Φ of check-ins. Since a user can visit the same place more than once, the presence of multiple links connecting users and places is possible if a temporal factor is considered. Therefore, a check-in is defined as a tuple θ = (x, t, ), where x ∈ V , t is the check-in time, and ∈ L. Clearly, θ ∈ Φ and |Φ| defines the total number of check-ins made by all users.

Link Prediction

In this section, we formally describe the link prediction problem and how this mining task is addressed in the LBSN domain. Moreover, we also review a selected number of friendship prediction methods for LBSNs.

Problem Description

Link prediction is a fundamental problem in complex network analysis [START_REF] Barabási | Network Science[END_REF][START_REF] Lü | Link prediction in complex networks: A survey[END_REF], hence in social network analysis [START_REF] Wu | A balanced modularity maximization link prediction model in social networks[END_REF][START_REF] Liu | Network growth and link prediction through an empirical lens[END_REF][START_REF] Valverde-Rebaza | Exploiting behaviors of communities of Twitter users for link prediction[END_REF][START_REF] Shahmohammadi | Presenting new collaborative link prediction methods for activity recommendation in Facebook[END_REF]. Formally, the link prediction problem aims at predicting the existence of a future or missing link among all possible pairs of nodes that have not established any connection in the current network structure [START_REF] Liben-Nowell | The link-prediction problem for social networks[END_REF].

Consider as potential link any pair of disconnected users x, y ∈ V such that (x, y) / ∈ E. U denotes the universal set containing all potential links between pairs of nodes in

V , i.e. |U | = |V |×(|V |-1)
Also consider a missing link as any potential link in the set of nonexistent links U -E. The fundamental link prediction task here is thus to detect the missing links in the set of nonexistent links, while scoring each link in this set. Thus, a predicted link is any potential link that has received a score above zero as determined by any link prediction method. The higher the score, the more likely the link will be [START_REF] Barabási | Network Science[END_REF][START_REF] Liben-Nowell | The link-prediction problem for social networks[END_REF][START_REF] Martínez | A survey of link prediction in complex networks[END_REF].

From the set of all predicted links, L p , obtained by use of a link prediction method, we assume the set of true positives (T P ) as all correctly predicted links, and the set of false positives (F P ) as the wrongly predicted links. Thus, L p = T P ∪ F P . Moreover, the set of false negatives (F N ) is formed by all truly new links that were not predicted.

Therefore, evaluation measures as the imbalance ratio, defined as IR = , can be used as well as the harmonic mean of precision and recall, the F-measure, defined as F 1 = 2 × P ×R P +R [START_REF] Scellato | Exploiting place features in link prediction on location-based social networks[END_REF][START_REF] Pham | Ebm: An entropy-based model to infer social strength from spatiotemporal data[END_REF]. However, most of the researches in link prediction consider that these evaluation measures do not give a clear judgment of the quality of predictions. For instance, a right predicted link could not be considered as a true positive if any link prediction method gives it a low score. To avoid this fact, two standard evaluation measures are used, AUC and precisi@L [START_REF] Valverde-Rebaza | Exploiting social and mobility patterns for friendship prediction in location-based social networks[END_REF][START_REF] Lü | Link prediction in complex networks: A survey[END_REF].

The area under the receiver operating characteristic curve (AUC) is defined as AU C = n1+0.5×n2 n , where from a total of n independent comparisons between pairs of positively and negatively predicted links, n 1 times the positively predicted links were given higher scores than negatively predicted links whilst n 2 times they were given equal scores. If the scores are generated from an independent and identical distribution, the AUC should be about 0.5; thus, the extent to which AUC exceeds 0.5 indicates how much better the link prediction method performs than pure chance. On the other hand, precisi@L is computed as precisi@L = Lr L , where L r is the number of correctly predicted links from L top-ranked predicted links.

Friendship Prediction in LBSNs

LBSNs provide services to their users to enable them to take better advantage of different resources within a specific geographical area, so the quality of such services can substantially benefit from improvements in link prediction [START_REF] Zhu | Understanding the adoption of location-based recommendation agents among active users of social networking sites[END_REF][START_REF] Valverde-Rebaza | Exploiting social and mobility patterns for friendship prediction in location-based social networks[END_REF]. Therefore, considering the natural heterogeneity of LBSNs, the link prediction problem for this type of network must consider its two kinds of links [START_REF] Bao | Recommendations in locationbased social networks: A survey[END_REF][START_REF] Zheng | Computing with Spatial Trajectories[END_REF], i.e. friendship prediction involves predicting user-user links [START_REF] Luo | Friendship Prediction Based on the Fusion of Topology and Geographical Features in LBSN[END_REF][START_REF] Xu-Rui | An algorithm for friendship prediction on location-based social networks[END_REF][START_REF] Valverde-Rebaza | Exploiting social and mobility patterns for friendship prediction in location-based social networks[END_REF] whilst location prediction focuses on predict user-location links [START_REF] Wang | A recommender system research based on location-based social networks[END_REF][START_REF] Pálovics | Locationaware online learning for top-k recommendation[END_REF][START_REF] Mcgee | Location prediction in social media based on tie strength[END_REF].

Friendship prediction is a traditional link prediction application, providing users with potential friends based on their relationship patterns and the social structure of the network [START_REF] Yu | Friend recommendation with content spread enhancement in social networks[END_REF]. Friendship prediction have been widely explored in LBSNs since it is possible to use traditional link prediction methods, such as common neighbors, Adamic-Adar, Jaccard, resource-allocation and preferential attachment, which are commonly applied and have been extensively studied in traditional social networks [START_REF] Lü | Link prediction in complex networks: A survey[END_REF][START_REF] Martínez | A survey of link prediction in complex networks[END_REF]. However, as location information is a natural resource in LBSNs, different authors have proposed friendship prediction methods to exploit it. Therefore, some methods use geographical distance [START_REF] Zhang | Distance and friendship: A distance-based model for link prediction in social networks[END_REF], GPS and/or check-in history [START_REF] Kylasa | Social ties and checkin sites: connections and latent structures in location-based social networks[END_REF], location semantics (tags, categories, etc.) [START_REF] Bayrak | Examining place categories for link prediction in location based social networks[END_REF] and other mobility user patterns [START_REF] Mengshoel | Will we connect again? machine learning for link prediction in mobile social networks[END_REF][START_REF] Pham | Ebm: An entropy-based model to infer social strength from spatiotemporal data[END_REF][START_REF] Xiao | Inferring social ties between users with human location history[END_REF] as information sources to improve the effectiveness of friendship prediction in LBSNs.

The friendship prediction task in LBSNs is still an open issue where there are constant advances and new challenges. Furthermore, the importance of the friendship prediction task is not only due to its well known application in friendship recommendation systems, but also because it opens doors to new research and application issues, such as companion prediction [START_REF] Liao | Who wants to join me?: Companion recommendation in location based social networks[END_REF], local expert prediction [START_REF] Cheng | Who is the Barbecue King of Texas?: A Geo-spatial Approach to Finding Local Experts on Twitter[END_REF][START_REF] Liou | Design of contextual local expert support mechanism[END_REF][START_REF] Niu | On local expert discovery via geo-located crowds, queries, and candidates[END_REF], user identification [START_REF] Rossi | It's the way you check-in: Identifying users in location-based social networks[END_REF][START_REF] Riederer | Linking users across domains with location data: Theory and validation[END_REF] and others.

Friendship Prediction Methods for LBSNs

Most existing link prediction methods are based on specific measures that capture similarity or proximity between nodes. Due to theirs low computational cost and easy calculation, link prediction methods based on similarity are candidate approaches for real-world applications [START_REF] Lü | Link prediction in complex networks: A survey[END_REF][START_REF] Xu-Rui | Using multi-features to recommend friends on location-based social networks[END_REF][START_REF] Narayanan | A study and analysis of recommendation systems for location-based social network (LBSN) with big data[END_REF].

Although there is abundant literature related to friendship prediction in the LBSN context, there is a lack of well organised and clearly explained taxonomy of existing methods in the current literature. For the sake of clearly arranging these existing methods, this study proposes a taxonomy for friendship prediction methods for LBSNs based on the information sources used to perform their predictions. Figure 1 shows the proposed taxonomy. Friendship prediction methods for LBSNs use three information sources to compute the similarity between a pair of users: check-in, place, and social information. In turn, each information source has specific similarity criteria. There-fore, methods based on check-in information explore the frequency of visits at specific places and information gain. Methods based on place information commonly explore the number of user visits, regardless of frequency, to distinct places as well as the geographical distance between places. Finally, methods based on social information explore the social strength among users visiting the same places.

Place Information Check-in Information

Here, we will give a systematic explanation of popular methods for friendship prediction in LBSNs belonging to each one of the proposed categories.

Methods based on Check-in Information

User mobility behaviors can be analyzed when the time and geographical information about the location visited are record at check-ins. The number of check-ins may be an indicator of users' preference for visiting a specific type of places and therefore, the key to establishing new friendships. Two of the most common similarity criteria used by methods based on check-in information are the check-in frequency and information gain.

Methods based on check-in frequency consider that the more check-ins at same places have made two users the more likely they will establish a friendship relationship. Some representative methods based on check-in frequency are the collocation, distinct collocation, Adamic-Adar of places, preferential attachment of check-ins, among others [START_REF] Cranshaw | Bridging the gap between physical location and online social networks[END_REF][START_REF] Mengshoel | Will we connect again? machine learning for link prediction in mobile social networks[END_REF][START_REF] Bayrak | Contextual feature analysis to improve link prediction for location based social networks[END_REF]. Bellow, we present the definition of two well-known friendship methods for LBSNs based on check-in frequency.

Collocation (Co). This is one of the most popular methods based on the checkin frequency. The collocation method, also referred to as the number of collocations or common check-in count, expresses the number of times that users x and y visited some location at the same period of time. Thus, for a pair of disconnected users x and y, and considering a temporal threshold of time, τ ∈ R, the Co method is defined as:

s Co x,y,τ = |Φ Co (x, y, τ)|, (1)
where, Φ Co (x, y, τ) = {(x, y, t x , t y , ) | (x, t x , ) ∈ Φ(x) ∧ (y, t y , ) ∈ Φ(y) ∧ |t x -t y | ≤ τ}, is the set of check-ins made by both users x and y at the same place and over the same period of time, and Φ(x) = {(x, t, ) | x ∈ V : (x, t, ) ∈ Φ} is the set of check-ins made by the user x at different places.

Adamic-Adar of Places (AAP). This is based on the traditional Adamic-Adar method but considering the number of check-ins of common visited places of users x and y. Thus, for a pair of users x and y, AAP is computed as:

s AAP x,y = ∈Φ L (x,y) 1 log |Φ( )| , (2)
where Although the number of check-ins may be a good indicator for the establishment of friendship between users, the fact that they have many check-ins at visited places may, on the contrary, reduce their chances of getting to know each other. To avoid this situation, some researchers have used the information gain of places as a resource to better discriminate whether a certain place is relevant to the formation of social ties between its visitors [START_REF] Cranshaw | Bridging the gap between physical location and online social networks[END_REF][START_REF] Scellato | Exploiting place features in link prediction on location-based social networks[END_REF][START_REF] Luo | Friendship Prediction Based on the Fusion of Topology and Geographical Features in LBSN[END_REF][START_REF] Bayrak | Contextual feature analysis to improve link prediction for location based social networks[END_REF]. Some methods based on information gain of places are min entropy, Adamic-Adar of entropy, location category and others. Bellow, we present two well-known friendship methods for LBSNs based on information gain.

Φ L (x, y) = Φ L (x) ∩ Φ L (y)

Adamic Adar of Entropy (AAE). This also applies the traditional Adamic-

Adar method while considering the place entropy for common locations of a pair of users x and y. Therefore, the AAE method is defined as:

s AAE x,y = ∈Φ L (x,y) = 1 log E( ) , (3)
where

E( ) = -x∈Φ V ( ) q x, log(q x, ) is the place entropy of location , q x, = |Φ(x, )| |Φ( )| is the relevance of check-ins of a user, Φ(x, ) = {(x, t, ) | (x, t, ) ∈ Φ(x) ∧ ∈ Φ L (x)} is the set of check-ins of a user x at location , and Φ V ( ) = {x | (x, t, ) ∈ Φ(x) ∧ ∈ Φ L (x)} is the set of visitors of location .
Location Category (LC). This calculates the total sum of the ratio of the number of check-ins of all locations visited by users x and y to the number of check-ins of users x and y at these locations while disregarding those with a high place entropy. Therefore, considering an entropy threshold τ E ∈ R, the LC method is defined as:

s LC x,y = ∈Φ L (x) ∧ E( )<τ E ∈Φ L (y) ∧ E( )<τ E |Φ( )| + |Φ( )| |Φ(x, )| + |Φ(y, )| . (4)

Methods based on Place Information

Friendship prediction methods based on place information consider that locations are the main elements on which different similarity criteria can be used. Two of the most common similarity criteria used by methods based on place information are the number of distinct visitations and geographical distance.

Methods based on distinct visitations consider specific relations among the different visited places by a pair of user as the key to compute the likelihood of a future friendship between them. Some representative methods based on distinct visitations at specific places are the common location, jaccard of places, location observation, preferential attachment of places, among others [START_REF] Cranshaw | Bridging the gap between physical location and online social networks[END_REF][START_REF] Steurer | Predicting social interactions from different sources of location-based knowledge[END_REF][START_REF] Steurer | Acquaintance or partner predicting partnership in online and location-based social networks[END_REF][START_REF] Scellato | Exploiting place features in link prediction on location-based social networks[END_REF]. Below, we present two of the most representative friendship prediction methods for LBSNs based on distinct visitations.

Common Location (CL)

. This is inspired by the traditional common neighbor method and constitute the simplest and most popular method based on distinct visitations at places to determine the homophily among pairs of users. Common location method, also known as common places or distinct common locations, expresses the number of common locations visited by users x and y. Thus, CL is defined as:

s CL x,y = |Φ L (x, y)|, (5)
where, Φ L (x, y) = Φ L (x) ∩ Φ L (y) is the previously defined set of common visited places of a pair of users x and y.

Jaccard of Places (JacP). This is inspired by the traditional Jaccard method. Jaccard of places method is defined as the fraction of the number of common locations and the number of locations visited by both users x and y. Therefore, JacP is computed as:

s JacP x,y = |Φ L (x, y)| |Φ L (x) ∪ Φ L (y)| . ( 6
)
On the other hand, since different studies have shown the importance of geographical or geospatial distance in the establishment of social ties, many authors have proposed to exploit this fact to improve friendship prediction. Some of the most representative methods based on geographical distance are the min distance, geodist, weighted geodist, Hausdorff distance and adjusted Hausdorff distance [START_REF] Scellato | Exploiting place features in link prediction on location-based social networks[END_REF][START_REF] Bayrak | Contextual feature analysis to improve link prediction for location based social networks[END_REF][START_REF] Zhang | Distance and friendship: A distance-based model for link prediction in social networks[END_REF][START_REF] Li | Geo-social media analytics[END_REF]. Below, we discuss two representative friendship prediction methods for LBSNs based on geographical distance.

GeoDist (GeoD). This method is the most common of those based on geographical distance. Consider as the "home location" of user x, h x , relative to the most checked-in place. Therefore, GeoD computes the geographical distance between the home locations of users x and y. Thus, GeoD is calculated as:

s GeoD x,y = dist( h x , h y ), (7)
where dist( , ) is simply the well-known Haversine formula to calculate the great-circle distance between two points and over the Earth's surface [START_REF] Goodwin | The haversine in nautical astronomy[END_REF]. It is important to note that for this case, two users are more likely to establish a friendship if they have a low GeoD value.

Adjusted Hausdorff Distance (AHD). This method is based on the classic Hausdorff distance but applying an adjustment to improve the friendship prediction accuracy. The AHD method is thus defined as:

s AHD x,y = max{ sup ∈Φ L (x) inf ∈Φ L (y) dist adj ( , ), sup ∈Φ L (y) inf ∈Φ L (x) dist adj ( , )}, (8)
where dist adj ( , ) = dist( , ) × max(diversity( ), diversity( )) is the adjusted geographical distance between two locations and , diversity( ) = exp(E( )) is the location diversity used to represent a location's popularity, and sup and inf represent the supremum (least upper bound) and infimum (greatest lower bound), respectively, from the set of visited places of a user x. Also similar to GeoD method, two users will be more likely to establish a relationship if they have a low AHD value.

Methods based on Social Information

Despite the fact that most of previously described methods capture different social behavior patterns based on the visited places of users, they do not directly use the social strength of ties between visitors of places [START_REF] Valverde-Rebaza | Exploiting social and mobility patterns for friendship prediction in location-based social networks[END_REF].

In the last years, some methods have been proposed to compute the friendship probability between a pair of users based on the places visited by their common friends. Some methods based on social strength are common neighbors within and outside of common places, common neighbors of places, common neighbors with total and partial overlapping of places and total common friend common check-ins [START_REF] Valverde-Rebaza | Exploiting social and mobility patterns for friendship prediction in location-based social networks[END_REF][START_REF] Bayrak | Contextual feature analysis to improve link prediction for location based social networks[END_REF]. Below, we describe two representative friendship prediction methods for LBSNs based on social strength.

Common Neighbors of Places (CNP). This indicates that a pair of users x and y are more likely have a future friendship if they have many common friends visiting the same places also visited by at least x or y. Thus, the CNP method is defined as:

s CN P x,y = |Λ L x,y |, (9)
where

Λ L x,y = {z ∈ Λ x,y | Φ L (x) ∩ Φ L (z) = ∅ ∨ Φ L (y) ∩ Φ L (z) =
∅} is the set of common neighbors of places of users x and y, and Λ x,y = {z ∈ V | (x, z) ∈ E ∧ (y, z) ∈ E} is the traditional set of common neighbors of pair of users x and y.

Common Neighbors with Total and Partial Overlapping of Places (TPOP).

This considers that a pair of users x and y could develop a friendship if they have more common friends visiting places also visited by both users than common friends who visited places also visited by only one of them. Therefore, the TPOP method is defined as:

s T P OP x,y = |Λ T OP x,y | |Λ P OP x,y | , (10)
where, Λ T OP

x,y

= {z ∈ Λ L x,y | Φ L (x)∩Φ L (z) = ∅∧Φ L (y)∩Φ L (z) =
∅} is the set of common neighbors with total overlapping of places, and

Λ P OP x,y = Λ L x,y -Λ T OP x,y
is the set of common neighbors with partial overlapping of places.

Proposals

We analyzed the reviewed link prediction methods and observed that some of them use more than one information source to improve their prediction accuracy. For example, AAP is naturally a method based on check-in frequency but it also use distinct visitations at specific places as additional information source. Other example is AHD, which is naturally a method based on geographical distance but it also use check-in frequency and information gain as additional information sources. Table 1 provides an overview of different information sources used by each friendship prediction method described in Section 3.3.

Table 1: Summary of the friendship prediction methods for LBSNs, from the literature and our proposals, as well as the information sources used to make their predictions. From Table 1 we found that some information sources were not combined, for instance, social strength is only combined with distinct visitations at specific places. Assuming that combination of some information sources could improve the friendship prediction accuracy, we propose five new methods referred to as check-in observation (ChO), check-in allocation (ChA), friendship allocation within common places (FAW), common neighbors of nearby places (CNNP) and nearby distance allocation (NDA). They are shown in bold in Table 1 and are described as follows:

Method

Check-in Observation (ChO). This is based on both the distinct visitations at specific places and check-in frequency to perform predictions. We define ChO method as the ratio of the sum of the number of check-ins of users x and y at common visited places to the total sum of the number of check-ins at all locations visited by these users. Thus, ChO is computed as:

s ChO x,y = ∈Φ L (x,y) |Φ(x, )| + |Φ(y, )| ∈Φ L (x) |Φ(x, )| + ∈Φ L (y) |Φ(y, )| . ( 11
)
Check-in Allocation (ChA). This is based on the traditional resource allocation method, ChA refines the popularity of all common visited places of users x and y through the count of total check-ins of each of such places. Therefore, ChA is defined as:

s ChA x,y = ∈Φ L (x,y) 1 |Φ( )| . ( 12
)
ChA heavily punishes high numbers of check-ins at popular places (e.g. public venues) by not applying a logarithmic function on the size of sets of all check-ins at these places. Similar to ChO, the ChA method is also based on both the distinct visitations at specific places and check-in frequency to work.

Friendship Allocation Within Common Places (FAW). This is also inspired by the traditional resource allocation method. Let the set of common neighbors within common visited places be Λ W CP

x,y

= {z ∈ Λ x,y | Φ L (x, y)∩ Φ L (z) = ∅},
the FAW method refines the number of check-ins made by all common friends within common visited places of users x and y. Therefore, the FAW is defined as:

s F AW x,y = z∈Λ W CP x,y 1 |Φ(z)| . ( 13
)
Despite the use of check-in frequency and distinct visitations at places by FAW, we consider that this method is mainly based on social strength, due to the fact that this criterion is the filter used to perform predictions.

Common Neighbors of Nearby Places (CNNP). This counts the number of common friends of users x and y whose geographical distance between their home locations and the home location of at least one, x or y, lies within a given radio. Therefore, given a distance threshold τ d , CNNP is computed as:

s CN N P x,y = |{z | ∀z ∈ Λ x,y ∧ (dist( h x , h z ) ≤ τ d ∨ dist( h y , h z ) ≤ τ d )}|. ( 14
)
CNNP uses full place information as well as social information to make predictions, however we consider that it is a method based on social strength due to the fact that this criterion is fundamental for CNNP to work.

Nearby Distance Allocation (NDA). This refines all the minimum adjusted distances calculated between the home locations of users x and y, and the respective home locations of all of their common neighbors of places. Therefore, NDA is defined as:

s N DA x,y = z∈Λ L x,y 1 min{dist adj ( h x , h z ), dist adj ( h y , h z )} . ( 15
)
NDA is the only method that uses full check-in, place and social information. However, as previously applied for the other proposals, since NDA uses social strength as the main criterion, we consider it to be a method based on social information.

Performance Evaluation

In this section, we present an experimental evaluation carried out for all link prediction methods previously studied. This section includes an analysis of three real-world LBSN datasets with which the experiments were performed as well as a deep analysis of the predictive capabilities of each evaluated method.

Dataset Description

The datasets used in our experiments are real-world LBSNs in which users made check-ins to report visits to specific physical locations. In this section, we describe their main properties and ways to construct the training and test datasets.

Dataset Selection

The datasets used for our experiments had to meet certain requirements: i) they had to represent social and location data, i.e. data defining existing connections between users as well as the check-ins of all of them at all of their visited locations, and ii) those connections and/or check-ins had to be time stamped. Based on these two criteria, we selected three datasets collected from real-world LBSNs, which are commonly used by the scientific community for mining tasks in the LBSN domain.

Brightkite. This was once a location-based social networking service provider where users shared their locations by checking-in. The Brightkite service was shut down in 2012, but the dataset was collected over the April 2008 to October 2010 period [START_REF] Cho | Friendship and mobility: User movement in location-based social networks[END_REF]. This publicly available dataset1 consists of 58228 users, 214078 relations, 4491144 check-ins and 772788 places.

Gowalla. This is also another location-based social networking service that ceased operation in 2012. The dataset was collected over the February 2009 to October 2010 period [START_REF] Cho | Friendship and mobility: User movement in location-based social networks[END_REF] and also is publicly available2 . This dataset contains 196591 users, 950327 relations, 6442892 check-ins and 1280969 different places.

Foursquare. Foursquare is one of the most popular online LBSN. Currently, this service report more than 50 million users, 12 billion check-ins and 105 million places in January 2018 3 . The dataset used for us experiments was collected over January 2011 to December 2011 period [START_REF] Gao | gscorr: Modeling geo-social correlations for new check-ins on location-based social networks[END_REF]. This publicly available dataset 4 contains 11326 users, 23582 relations, 2029555 check-ins and 172044 different places.

The various properties of these datasets were calculated an the values depicted in Table 2. This table is divided into two parts, the first shows topological properties [START_REF] Barabási | Network Science[END_REF] whilst the second shows location properties [START_REF] Zheng | Computing with Spatial Trajectories[END_REF][START_REF] Valverde-Rebaza | Exploiting social and mobility patterns for friendship prediction in location-based social networks[END_REF]. Therefore, considering the first part of Table 2 we observe that the analyzed networks have a small average degree, k , which suggests that the users of these networks had between 4 and 10 friends in average. This implies that the average clustering coefficient, C, of networks is also low. However, the low degree heterogeneity, H = k 2 k 2 , of Brightkite and Foursquare indicate that their users are less different from each other than the users of Gowalla. Also, the assortativity coefficient r, which measures the preference of users to attach to others, shows that only Brightkite is assortative, which is why it has a positive value, indicating the presence of few relationships among users with a similar degree. On the other hand, Gowalla and Foursquare are disassortative, since their assortativity coefficients are negative, indicating the presence of a considerable number of relationships among users with a different degree. Considering the second part of Table 2, we observe that the number of users with at least one check-in, |Φ V |, is a little over 85% of total users of networks. Despite the fact that Gowalla and Brightkite have more users and check-ins than Foursquare, the average number of check-ins per user, Φ , of Foursquare users is greater than that of Gowalla and Brightkite users. However, the average of check-ins per place, L Φ , is similar for Brightkite and Gowalla, whilst for Foursquare is greater, i.e. Foursquare users made more check-ins at a specific place than Brightkite and Gowalla users. Finally, the very small average place entropy, E = 1 |L| ∈L E( ), of Brightkite suggests that the location information in this LBSN is a stronger factor to facilitate the establishment of new relationships between users than for Gowalla and Foursquare users.

Data Processing

We preprocess the datasets to make the data suitable for our experiments. Considering that isolated nodes and locations without visits can generate noise when measuring the performance of different link prediction methods, it is necessary to apply a policy for selecting data samples containing more representative information. Therefore, for each dataset, we consider only users with at least one friend and with at least one check-in at any location.

Since our goal is to predict new friendships between users, we divided each dataset into training and test (or probe) sets while taking the time stamps information available into account. Therefore, links formed by Brightkite users who checked-in from April 2008 to January 2010 were used to construct the training set, whilst links formed by users who checked-in from February 2010 to October 2010 were used for the probe set. For Gowalla, the training set was constructed with links formed by users who checked-in from February 2009 to April 2010, and the probe set was constructed with links formed by users who checked-in from May 2010 to October 2010. Whereas, for Foursquare the training set is formed by users who checked-in from January 2011 to September 2011, whilst the probe set is formed by users that made check-ins over the October 2011 to December 2011 period. Table 3 shows the training and testing time ranges for the three datasets. Different studies have used a similar strategy for splitting data into training and probe sets, but they were not concerned about maintaining the consistency between users in both sets [START_REF] Valverde-Rebaza | Exploiting social and mobility patterns for friendship prediction in location-based social networks[END_REF][START_REF] Bayrak | Contextual feature analysis to improve link prediction for location based social networks[END_REF][START_REF] Luo | Friendship Prediction Based on the Fusion of Topology and Geographical Features in LBSN[END_REF], which could affect the performance of link prediction methods in different ways [START_REF] Yang | Evaluating link prediction methods[END_REF]. To avoid that, we proceeded to remove all links formed by users who checked-in only during the training time range or only in the testing time range. From the links formed by users with check-ins in both the training and testing time ranges, we chose one-third of the links formed by users at random with a higher degree than the average degree for the probe set, while the remaining links were part of the training set. Therefore, we obtained the training set G T (V, E T , L, Φ T ) and probe set G P (V, E P , L, Φ P ), where both sets keep the same users (V ) and locations (L) but differ in the social (E T and E P ) and user-location (Φ T and Φ P ) links.

Table 3

Data Limitations

Although the datasets selected contain thousands of users and links, they can be considered as relatively small compared to other online social network datasets. Notwithstanding this limitation present in the datasets analyzed in this study, we use them since they meet the requirements explained previously in Section 5.1.1 and also because they are frequently used in the state-of-the-art in order to propose a quantitive and qualitative analysis on the social and spatial factors impacting the friendships [START_REF] Allamanis | Evolution of a location-based online social network: Analysis and models[END_REF][START_REF] Cho | Friendship and mobility: User movement in location-based social networks[END_REF][START_REF] Mengshoel | Will we connect again? machine learning for link prediction in mobile social networks[END_REF][START_REF] Bayrak | Contextual feature analysis to improve link prediction for location based social networks[END_REF]. Therefore, this work offers new light on exploiting the different information sources to improve friendship prediction in Brightkite, Gowalla and Foursquare, but our findings could be applied for other LBSNs.

Some studies of the state-of-the-art use other datasets, e.g. Foursquare [START_REF] Luo | Friendship Prediction Based on the Fusion of Topology and Geographical Features in LBSN[END_REF][START_REF] Zhang | Transferring heterogeneous links across location-based social networks[END_REF], Facebook [START_REF] Mcgee | Location prediction in social media based on tie strength[END_REF], Twitter [START_REF] Zhang | Transferring heterogeneous links across location-based social networks[END_REF], Second Life [START_REF] Steurer | Predicting social interactions from different sources of location-based knowledge[END_REF][START_REF] Steurer | Acquaintance or partner predicting partnership in online and location-based social networks[END_REF], and other LBSNs. But we cannot use them for two main reasons: i) generally they are not publicly available, and ii) they do not respect the requirements detailed in Section 5.1.1.

Experimental Setup

For each of the 10 independent partitions of each dataset obtained as explained in Section 5.1.2, we considered 10 executions of each link prediction method presented in Section 3 and our proposals described in Section 4. We then applied different performance measures to the prediction results to determine which were the most accurate and efficient link prediction methods.

All of the evaluation tests were performed using the Geo-LPsource framework, which we developed and is publicly available 5 . We set the default parameters of the link prediction methods as follows: i) for Co method we considered that τ = 1 day, ii) for LC method we considered that τ E = E , iii) for CNNP method we considered that τ d = 1500 m., and iv) for AHD method, for a user x and being the most visited place by him, we considered that the comparison .

Evaluation Results

For the three LBSNs analyzed, Table 4 summarizes the performance results for each link prediction method through different evaluation metrics. Each value in this table was obtained by averaging over 10 runs, over 10 partitions of training and testing sets, as previously detailed in Section 5.2. The values highlighted in bold correspond to the best results achieved for each evaluation metric. From Table 4, imbalance ratio and F-measure results were calculated considering the whole list of predicted links obtained by each evaluated link prediction method. On the other hand, the AUC results were calculated from a list of n = 5000 pairs of wrongly and right predicted links chosen randomly and independently. Due to the number of link prediction methods studied and the different ways they were evaluated, we performed a set of analyses to determine which were the best friendship prediction methods for LBSNs.

Reducing the Prediction Space Size

The prediction space size is related to the size of the set of predicted links, L p . Most existing link prediction methods prioritize an increase in the number of correctly predicted links even at the cost of a huge amount of wrong predictions. This generates a extremely skewed distribution of classes in the prediction space, which in turn impairs the performance of any link prediction method [START_REF] Scellato | Exploiting place features in link prediction on location-based social networks[END_REF]. Therefore, efforts should also focus not only on reducing the number of wrong predictions but also on increasing the number of correctly predicted links relative to the total number of predictions.

Previous studies showed that the prediction space size of methods based only on the network topology is around 10 11 ∼ 10 12 links for Brightkite and Gowalla. However, by using methods based on location information, the prediction space can be reduced by about 15-fold or more [START_REF] Valverde-Rebaza | Exploiting social and mobility patterns for friendship prediction in location-based social networks[END_REF][START_REF] Scellato | Exploiting place features in link prediction on location-based social networks[END_REF]. Based on that and to determine if reduction of the prediction space is related to different information sources, in Figure 2 we report the average prediction space size of the different link prediction methods analyzed in this study. Figure 2 shows that for the analyzed networks, methods based on checkin frequency, information gain, distinct visitations at places and geographical distance, followed the traditional logic of obtaining a high number of right predictions at the cost of a much higher number of wrong predictions [START_REF] Wang | Human mobility, social ties, and link prediction[END_REF]. On the other hand, methods based on social strength led to a considerably lower number of wrong predictions at the cost of a small decrease in the number of correctly predicted links relative to the results obtained by the first cited methods, which is important in a real scenario [START_REF] Valverde-Rebaza | Exploiting social and mobility patterns for friendship prediction in location-based social networks[END_REF]. Our proposals followed a similar scheme as methods based on social strength, leading to less wrong predictions.

G1 G2 G3 G4 G5 G6 10
This fact is clearly shown by the IR results in Table 4 where, besides highlighting that Co method generally had a better IR performance, we observed that some methods based on check-in frequency, information gain, distinct visitations at places and geographical distance had an IR higher than most methods based on social strength and our proposals. Therefore, Co was the method with the overall best IR performance, whilst GeoD and AHD were the worst ones.

Considering only our proposals, we found that FAW and CNNP performed better in IR. These two methods have social components, which help to significantly reduce the prediction space size. The worst IR performance of our proposals was obtained by NDA, which is based on geographical distance, thus confirming that this type of information source generates a large prediction space.

Measuring the Accuracy

Since the IR results shown that some methods obtained a considerable number of correctly predicted links whilst others obtained an absurdly large number of wrongly predicted links, we adopted the f-measure (F 1 ) to evaluate the performance of prediction methods in terms of relevant predicted links. Therefore, we observe that FAW method, which is one of our proposals, had the best f-measure performance in the three analyzed LBSNs.

To facilitate the analysis of all link prediction methods, based on Table 4 we ranked the average F 1 results obtained by all the link prediction methods in the three analyzed networks, and then we applied the Friedman and Nemenyi posthoc tests [START_REF] Demšar | Statistical comparisons of classifiers over multiple data sets[END_REF]. Therefore, the F-statistics with 14 and 28 degrees of freedom and at the 95 percentile was 2.06. According to the Friedman test using Fstatistics, the null-hypothesis that the link prediction methods behave similarly when compared with respect to their F 1 performance should be rejected. and TPOP, performed better than the others since occupied the first and second position, respectively. Co and ChO are in third and fourth position, respectively, whilst JacP and CL tied for the fifth position. After these methods, and a little further away, we have that ChA, AAP and AAE tied for the sixth position, CNNP and NDA are in seventh and eight position, respectively. CNP is ninth, AHD is tenth , GeoD is eleventh and LC is twelfth. Therefore, we observe that two of our proposals, FAW and ChO, are in the top-5. Moreover, methods based on information gain, such as LC, and methods based on geographical distance, such as GeoD and AHD, were at the end of the ranking.

Analyzing the Predictive Power

Table 4 also shows the prediction results obtained for AUC. From these results, we observed that CNP, GeoD and JacP outperformed all the other link prediction methods in Brightkite, Gowalla and Foursquare, respectively. In addition, we found that all the link prediction methods performed better than pure chance, except for LC in Foursquare.

Furthermore, to gain further insight into the real prediction power of evaluated link prediction methods, we followed the same scheme used previously for F 1 analysis. Therefore, we ranked the average results of AUC obtained by all the link prediction methods, and then we applied Friedman and Nemenyi post-hoc tests. Similarly that for F 1 analysis, the critical value of the F-statistics with 14 and 28 degrees of freedom and at the 95 percentile was 2.06. However, unlike the F 1 analysis, this time the Friedman test suggested that the null-hypothesis that the link prediction methods behave similarly when compared by their AUC performance should not be rejected.

Figure 3(b) shows the Nemenyi test results for the evaluated methods ranked by AUC. The diagram indicates that the CD value calculated at the 95 percentile was 12.38. This test also showed that the link prediction methods have no statistical significant difference, so they are connected by a bold line.

Figure 3(b) indicates that, differently from F 1 analysis, this time the methods based on geographical distance and information gain are in the firsts positions. Thus, GeoD and AAE are in first and second position, respectively. JacP is third whilst FAW and ChA tied for the fourth position and AAP is fifth. The rest of the ranking was in the following order: NDA, CNP, AHD, ChO, CL, TPOP, Co, CNNP and LC. In this ranking, we also have two of our proposals in the top-5. FAW and ChA. To our surprise, LC continues in last position and some methods that have performed well in the F 1 ranking, such as TPOP, Co and CL, this time were in compromising positions.

Obtaining the Top-5 Friendship Prediction Methods

Since some link prediction methods performed better in the prediction space analysis whilst other ones did in the prediction power analysis, we analyzed the F 1 and AUC results at the same time. Therefore, from Table 4 we ranked the average F 1 and AUC results obtained by all the link prediction methods, and then applied Friedman and Nemenyi post-hoc tests to them. The critical F-statistic value with 14 and 70 degrees of freedom and at the 95 percentile was 1.84. Based on this F-statistic, the Friedman test suggested that the nullhypothesis that the methods behave similarly when compared according to their F 1 and AUC performances should be rejected.

Figure 4 shows the Nemenyi test results for the analyzed methods in our final ranking. The diagram in Figure 4 indicates that the CD value at the 95 percentile is 8.76. From diagram in Figure 4, we observe that FAW has statistical significant difference with LC. 4. Diagram shows the final ranking of link prediction methods considering both the optimal reduction of prediction space size and high prediction power. Our proposals are highlighted in bold.

Figure 4 indicates that FAW is in first position, JacP is second, AAE is third, ChA is fourth and AAP is fifth. ChO and TPOP tied for the sixth position. The rest of the ranking was in the following order: CL, GeoD, NDA, Co, CNP, AHD, CNNP and LC. Therefore, two of our proposals, FAW and ChA, are in the top-5 of the final ranking. LC definitively has the worst performance. Note that the methods in the top-5 belong to the different information sources identified in this study, so we have a method based on social strength (FAW), a method based on distinct visitations at places (JacP), a method based on information gain (AAE) and two methods based on check-in frequency (ChA and AAP). The only one missing in the top-5 of the final ranking is some method based on geographical distance.

For recommending to users some links as possible new friendships, we can just select the links with the highest scores [START_REF] Liben-Nowell | The link-prediction problem for social networks[END_REF][START_REF] Lü | Link prediction in complex networks: A survey[END_REF][START_REF] Valverde-Rebaza | Exploiting social and mobility patterns for friendship prediction in location-based social networks[END_REF]. Furthermore, whereas for recommendation task is not enough only a method with good prediction performance, also it is necessary that from a limited portion of the total predicted links it generates a high number of right predictions, good enough to be showed to users as appropriate friendship suggestions [START_REF] Pálovics | Locationaware online learning for top-k recommendation[END_REF][START_REF] Ahmadian | A social recommendation method based on an adaptive neighbor selection mechanism[END_REF]. Therefore, to assess the performance of top-5 methods from the final ranking through limited segments of the total list of predicted links, we analyzed them by precisi@L. Figure 5 shows the different precisi@L performances for the top-5 methods of our final ranking. These precisi@L results were calculated for different L values and for each analyzed LBSN.

Figure 5 indicates that most of the evaluated methods performed best when L = 100, i.e. they are able to make a few accurate predictions. When link prediction methods have to make more than a thousand predictions, i.e when L > 1000, their prediction abilities decrease considerably. Moreover, Figure 5 shows that the evaluated methods have a similar behavior in the three analyzed LBSNs. Thus, ChA, AAP and AAE performed similarly with a slight superiority of ChA. Moreover, JacP and FAW showed similar performance with a slight superiority of JacP. Analyzing the precis@n performance of methods in each analyzed network, Figure 5(a) shows that in Brightkite, AAP outperformed all the other evaluated methods when L = 100. Thereafter, our proposal FAW performed better than the rest of methods for the rest of L values. JacP outperformed poorly. Figure 5(b) shows that in Gowalla, the methods JacP achieved the best performance for all of the L values. One of our proposals, i.e. ChA, ranks second when L = 100, to remain in third position for the rest of L values. When L = 1000, other of our proposals, i.e. FAW, achieve the second position and it holds that position for the rest of L values. Finally, Figure 5(c) shows that methods in this network achieved very low precisi@L values (less than 0.2). However, in Foursquare, ChA outperformed all the methods when L = 100 but it is overcome by JacP, which keeps the second position for the rest of L values. Our proposal FAW performed poorly when L = 100 but it achieves the third position when L = 1000 and maintain this position since it slightly exceeds AAE and AAP.

Conclusion

In last years, a variety of online services which provide users with easy ways to share their geo-spatial locations and location-related content have become popular. These services, called LBSNs, constitute a new type of social network and give rise to new opportunities and challenges with regard to different social network issues, such as location recommendation [START_REF] Mcgee | Location prediction in social media based on tie strength[END_REF][START_REF] Wang | A recommender system research based on location-based social networks[END_REF][START_REF] Pálovics | Locationaware online learning for top-k recommendation[END_REF], user identification [START_REF] Rossi | It's the way you check-in: Identifying users in location-based social networks[END_REF][START_REF] Riederer | Linking users across domains with location data: Theory and validation[END_REF], discovery of local experts [START_REF] Cheng | Who is the Barbecue King of Texas?: A Geo-spatial Approach to Finding Local Experts on Twitter[END_REF][START_REF] Liou | Design of contextual local expert support mechanism[END_REF][START_REF] Niu | On local expert discovery via geo-located crowds, queries, and candidates[END_REF], and discovery of travel companions [START_REF] Liao | Who wants to join me?: Companion recommendation in location based social networks[END_REF]. Motivated by the important role that LBSNs are playing for millions of users, we conducted a survey of recent related research on friendship prediction and recommendation.

Although there is abundant methods to tackle the friendship prediction problem in the LBSN domain, there is a lack of well organised and clearly explained taxonomy that helps the best use of current literature. Therefore, our first contribution in this work was related to proposes a taxonomy for friendship prediction methods for LBSNs based on five information sources identified: frequency of check-ins, information gain, distinct visitations at places, geographical distance and social strength.

Based on the taxonomy proposed, we identified some gaps in existing friendship prediction methods and proposed five new ones: check-in observation (ChO), check-in allocation (ChA), friendship allocation within common places (FAW), common neighbors of nearby places (CNNP) and nearby distance allocation (NDA). These new friendship prediction methods are exclusive to perform friendship prediction task in the LBSN context and constituted our second contribution.

Due to the fact that we aimed objectively quantify the predictive power of friendship prediction methods in LBSNs as well as determine how good they work in the context of recommender systems, our third contribution is related to the identification of the top-5 friendship prediction methods that better perform in the LBSN context. For this purpose, we performed an exhaustive evaluation process on snapshots of three well known real-world LBSNs.

Based on our results, we empirically demonstrate that some friendship prediction methods for LBSNs could be ranked as the best for some evaluation measure but could perform poorly for other ones. Thus, we stressed the importance of choosing the appropriate measure according to the objective pursued in the friendship prediction task. For instance, in general, some friendship prediction methods performed better with regard to the F-measure than with AUC, so if in any real-world application it is necessary to focus on minimizing the number of wrong predictions, the best option is to consider methods that work well based on the F-measure. However, if the focus is to obtain a high number of right predictions, but with a high chance that these predictions represent strong connections, then the best option could be to consider methods that work well based on AUC.

Nevertheless, in a real-world scenario likely will be necessary to balance both the F-measure and AUC performance of methods. Thus, we finally identified the top-5 friendship prediction methods that performed in a balanced way for different metrics. Moreover, in this top-5 are two of our proposals, FAW in the first position and ChA in the fourth.

Other observation based on our results is related to the fact that the use of a variety of information sources does not guarantee the best performance of a method. For instance, NDA method, which is one of our proposals, is the only one that uses all the information sources identified, but it appears in the ninth position of our final ranking. Finally, we also observe that methods based purely on check-in information or place information performed worse than methods combining these information sources with social information. Therefore, we have empirical foundation to support the argument that the best way to cope with friendship prediction problem in the LBSN context is by combining social strength with location information.

The future directions of our work will focus on location prediction, which will be used to recommend places that users could visit. For that, we hope that the location information sources identified in this work can also be used in the location prediction task.

  |Lp| |T P | , precision, defined as P = |T P | |T P |+|F P | , and recall, defined as R = |T P | |T P |+|F N |

  friendship prediction methods in LBSNs

Figure 1 :

 1 Figure 1: Information sources and the different similarity criteria used by existing methods to perform friendship prediction in LBSNs.

  is the set of places commonly visited by users x and y, Φ L (x) = { | ∀ ∈ L : (x, t, ) ∈ Φ(x)} is the set of distinct places visited by user x, and Φ( ) = {(x, t, ) | ∈ L : (x, t, ) ∈ Φ}, is the set of check-ins made by different users at location .

Check

  also summarizes the average number of users, |V | , average number of different locations, |L| , average number of training social links, |E T | and average number of testing social links, |E P | , obtained by averaging 10 independent partitions of each dataset. It is important to comment that, for the three datasets, the average number of check-ins in training set, |Φ P | , is twothirds of the total number of check-ins whilst the average number of check-ins in probe set, |Φ T | , is the remainder part.

Figure 2 :

 2 Figure 2: Number of correctly and wrongly predicted links for methods based on checkin frequency (G 1 ), information gain (G 2 ), distinct visitations at places (G 3 ), geographical distance (G 4 ), social strength (G 5 ) and our proposals (G 6 ) for (a) Brightkite, (b) Gowalla and (c) Foursquare. The dashed horizontal lines indicate the number of truly new links (links into the probe set) for each dataset. Results averaged over the 10 analyzed partitions and plotted in log 10 scale.

Figure 3 (

 3 a) shows the Nemenyi test results for the 15 analyzed link prediction methods considering the F 1 ranking. The critical difference (CD) value for comparing the mean-ranking of two different methods at the 95 percentile was 12.38, as shown on the top of the diagram. The method names are shown on the axis of the diagram, with our proposals highlighted in bold. The lowest (best) ranks are on the left side of the axis. Methods connected by a bold line in the diagram have no statistical significant difference, so the Nemenyi test indicated that FAW has statistical significant difference with LC and GeoD.

Figure 3 :

 3 Figure 3: Nemenyi post-hoc test diagrams obtained from (a) f-measure and (b) AUC results showed in Table4. Our proposals are highlighted in bold.

Figure 3 (

 3 Figure 3(a) indicates that methods based on social strength, such as FAW

Figure 4 :

 4 Figure 4: Nemenyi post-hoc test diagram obtained over the F 1 and AUC average ranks showed in Table4. Diagram shows the final ranking of link prediction methods considering both the optimal reduction of prediction space size and high prediction power. Our proposals are highlighted in bold.

Figure 5 :

 5 Figure 5: Precisi@L performance for the top-5 methods of the final ranking considering different L values for (a) Brightkite, (b) Gowalla and (c) Foursquare.

Table 2 :

 2 The main properties of the experimental LBSNs.

		Brightkite Gowalla Foursquare
	|V |	58228	196591	11326
	|E|	214078	950327	23582
	k	7.35	9.66	4.16
	C	0.17	0.24	0.06
	H	8.66	31.71	7.66
	r	0.01	-0.03	-0.07
	|Φ|	4491144	6442892	202955
	|Φ V |	50686	107092	9985
	Φ	88	60	179
	|L|	772788	1280969	172044
	L Φ	5	5	11
	E	0.05	0.25	0.19
	3 https://foursquare.com/about
	4 http://www.public.asu.edu/˜hgao16/Publications.html

Table 3 :

 3 Details of pre-processed datasets.

	Dataset	Training time range Testing time range	|V |	|L|	|E T |	|E P |
	Brightkite	2008/04 -2010/01	2010/02 -2010/10	4606 277515 49460	24800
	Gowalla	2009/02 -2010/04	2010/05 -2010/10	19981 607094 232194 87619
	Foursquare	2011/01 -2011/09	2011/10 -2011/12	7287 101546 12258	8565

Table 4 :

 4 Friendship prediction results for Brightkite, Gowalla and Foursquare. Highlighted values indicate the best results for each evaluation metric considered.

	Method		IR	F1	AUC		IR	F1	AUC		IR	F1	AUC
	Co		4.934 0.070	0.668		14.972 0.051	0.554		4.488 0.045	0.554
	AAP		13.190 0.104	0.682		36.531	0.045	0.728		13.367 0.034	0.655
	AAE		13.190 0.104	0.694		36.586	0.045	0.736		13.367 0.034	0.670
	LC		34.000 0.055	0.629		180.945 0.011	0.542		27.844 0.017	0.470
	CL		13.114 0.105	0.676		36.327	0.045	0.682		13.368 0.034	0.630
	JacP		13.114 0.105	0.630		36.327	0.045	0.742		13.368 0.034 0.708
	GeoD AHD CNP	Brightkite	35.005 0.053 31.689 0.056 31.180 0.060 0.761 0.710 0.685	Gowalla	180.461 0.011 0.767 223.714 0.011 0.681 66.484 0.029 0.687	Foursquare	35.710 0.018 35.782 0.018 23.277 0.027	0.705 0.656 0.608
	TPOP		13.441 0.105	0.673		25.383	0.057	0.665		12.588 0.036	0.594
	ChO		13.079 0.104	0.608		31.197	0.050	0.714		13.292 0.034	0.671
	ChA		13.173 0.104	0.676		36.460	0.045	0.736		13.367 0.034	0.667
	FAW		9.678 0.113 0.740		15.821 0.069 0.718		7.764 0.046 0.642
	CNNP		9.387	0.048	0.552		18.868	0.046	0.620		4.920	0.039	0.569
	NDA		22.496 0.076	0.700		47.540	0.037	0.720		15.325 0.024	0.624

since G is an undirected network.

http://snap.stanford.edu/data/loc-brightkite.html

http://snap.stanford.edu/data/loc-gowalla.html

https://github.com/jvalverr/Geo-LPsource

Acknowledgments

This research was partially supported by Brazilian agencies FAPESP (grants 2015/14228-9 and 2013/12191-5), CNPq (grant 302645/2015-2), and by the French SONGES project (Occitanie and FEDER).


G Bresson

A Ahmadi-Sénichault

O Caty

V Ayvazyan

M L L Gregori

S F Costa

G L Vignoles

Thermographic and tomographic methods for tridimensional characterization of thermal transfer in silica/phenolic composites

Keywords: A. Polymer-Matrix Composites (PMCs), B. thermal properties, C. Computational modeling, D. Non-destructive testing; D. X-ray tomography, D. Thermal Analysis

thermal properties are compared. Several experimental methods have been used, including space-resolved diffusivity determinations. Numerical results are compared to experimental ones in terms of transverse and longitudinal thermal conductivities of the composites, and were found to be in good agreement. A discussion is made on the different possible sources of uncertainty for both methods.

Nomenclature

Roman letters a

Thermal diffusivity (m 2 s -1 ) c p Mass thermal capacity (J K - Longitudinal macroscopic thermal conductivity of a composite (Wm -1 K -1 )

Introduction:

The development of new composites with low weight and high performance is an important issue for the production of thermal protection systems (TPS) for atmospheric re-entry of space objects [START_REF] Laub | Thermal Protection System Technology and facility Needs for Demanding Future Planetary Missions[END_REF]. Among them, silica-phenolic composites have shown excellent thermal performances [START_REF] Dauchier | Matériaux composites phénoliques ablatifs[END_REF], and very good ablation resistance [START_REF] Sykes | Decomposition characteristics of a char-forming phenolic polymer used for ablative composites[END_REF][START_REF] Kanno | Development of ablative material for planetary entry[END_REF]. In order to reduce processing costs and to optimize the material with respect to its mission, recent works [START_REF] Gregori | Mechanical and Ablative Properties of Silica-Phenolic Composites for Thermal Protection[END_REF][START_REF] Gregori | Ablative and mechanical properties of quartz phenolic composites[END_REF] have focused on the fabrication and characterization of composites in which the reinforcement is in the form of discontinuous chopped fabric pieces. This kind of improvement has been studied on aramid/epoxy composites [START_REF] Sohn | Mode II delamination toughness of carbon-fibre/epoxy composites with chopped kevlar fibre reinforcement[END_REF], and more generally on polymer-matrix composite prepregs for damage tolerance through mechanical testing [START_REF] Greenhalgh | The assessment of novel materials and processes for the impact tolerant design of stiffened composite aerospace structures[END_REF]. The result is an elimination of the tendency of the material to delaminate [START_REF] Gregori | Mechanical and Ablative Properties of Silica-Phenolic Composites for Thermal Protection[END_REF], as compared to the same material with 2D continuous fabric layup reinforcement, but at the expense of some abatement in mechanical properties like stiffness [START_REF] Kumar | Thermo-structural analysis of composite structures[END_REF].

In this paper, we focus on the determination of the thermal properties for this class of materials, comparing the « chopped » arrangement to the continuous fabric layup.

Two approaches will be developed in parallel and compared to each other. First, thermal measurements are performed by flash, hot disk and DSC methods. Second, the material structure assessed by microscopy and tomography and the properties of the components are used in an ad-hoc numerical procedure to predict the effective thermal diffusivity of the composite. The simultaneous development of these methods aims to contribute to the creation of a « material design tool » which can predict the influence of the reinforcement architecture on the effective thermal diffusivity or conductivity of the composite.

The materials and methods are first described; then, results from the thermographic and tomographic methods are presented and discussed.

Materials

The studied material samples were processed by Plastflow Ltd, Curitiba, Brazil, from a regular fabric, about 0.9 mm thick, of pure silica with an areal mass of 680 g/m 2 and a phenolic resin with 165 mPa.s viscosity, used at room temperature to obtain the prepreg material [START_REF] Gregori | Ablative and mechanical properties of quartz phenolic composites[END_REF]. Two configurations of the silica fiber reinforcement were studied (Figure 1). The first one is obtained by simply stacking the as-received prepreg layers, while the other one was made from the same prepregs, but in a chopped form. The "chopped fabric" composite is composed of a random arrangement of small, approximately square pieces of prepreg with an edge size of 20 to 28 mm. The two kinds of reinforcements are placed in multilayer configurations to obtain plates. Then, a hot compression process (15 min./70 bar/175ºC) and a second cure are applied to both materials (12h/1 atm/180°C). The final dimensions are 240 × 240 × 8 mm 3 .

Experimental methods

Properties of the components

Individual components were tested and data are reported in Table 1. Density measurements were made with an Accupyc 1330 He pycnometer; the results are consistent with ref.

[5]. The fiber average diameter was estimated using microscopic observations on approximately 350 fibers. The matrix thermal properties were obtained using flash thermography (diffusivity) and DSC (heat capacity). The fiber heat capacity was obtained by subtraction between the composite and the matrix values, and its diffusivity by a specific laser excitation method [START_REF] Vignoles | Measurement of the thermal diffusivity of a silica fiber bundle using a laser and an IR camera[END_REF]. The reported values will be used in the numerical computations based on tomographic images.

For each composite, the analysis of phase ratios was performed using Hg porosimetry (open porosity, skeletal density, and bulk density), combined to 3D (X-ray tomography) and 2D (optical microscopy) imaging. The results are synthesized in Table 1.

Thermal methods

Thermal analyses were done to obtain conductivities to validate numerical results.

These values are also used to compare materials thermal behaviors. Firstly, an infrared thermographic analysis by a flash method was performed to experimentally measure the thermal diffusivity field (a) of the plates averaged through their thickness. The thermal diffusivity is essential to determine the thermal conductivity (λ) when the mass thermal capacity (c p ) and the density (ρ) are known, since a is λ/ρc p . This method consists in applying a photothermal pulse -the flash -on the front face of the material and measuring the evolution of the temperature on the rear face. The technique described by Degiovanni et al. [START_REF] Degiovanni | Diffusivité thermique et méthode flash[END_REF] has been found more appropriate than the traditional method of Parker et al. [START_REF] Parker | Flash method of determining thermal diffusivity, heat capacity, and thermal conductivity[END_REF], because of non-negligible thermal losses; it has been applied here on IR camera data for both composite samples, in both directions, and for the pure matrix.

The average of the camera-recorded thermal field was used as the signal to be processed. It should be noted that the direction perpendicular to the composite plates will be called transverse, while those parallel to the plate will be called longitudinal.

The experimental setup is composed of a flashlight device (Elinchrom Style RX1200) acting on the front face of the composite sample and an IR camera (FLIR SC7000, 320 × 256 pixels) recording periodically (25 Hz) thermal images on the rear face. Adiabatic conditions were ensured on the sample sides by inserting them inside a PS foam holder. The flash impulsion is spread on the entire front face (30 × 30 mm 2 ) so as to place the sample in 1D heat transfer conditions. All samples being semi-translucid, their flashed face was painted in black.

The hot disk method [13,14] was also used to validate the values measured by thermography and to obtain the thermal conductivities in the principal directions. The measurements were performed with a TPS 2500 device by Hot Disk AB (Sweden).

DSC measurements were carried out on a Setaram Labsys TM 131 Evo apparatus, with a 5°C/min heating rate, between ambient temperature and 110°C.

Calculations

The model used to calculate the diffusivity and conductivity is based on 2D/3D image analysis and on a double change of scale. The method is described in ref.

[19] for a fibrous C/C composite but is also efficient for a large number of fibrous composites when µCT images of the material at different scales are available.

Imaging

The arrangement of fibers, pores and matrix, responsible of the specific thermal properties of the composites, exhibits two scales of heterogeneity that must be analyzed successively. They are illustrated in Figure 2. Standard micrographic imaging of transverse sections of yarns (Figure 2d) is sufficient to extract the structural information at this scale, the fibers being mostly parallel to each other. The lowresolution images (Figures 2a,b,c) provide information only on the weaving pattern in the representative elementary volume (REV), but a 3D information is needed for accuracy; therefore, X-ray tomographs have been also used.

Micrographs were acquired on a standard optical microscope (Nikon Eclipse ME600) and a numerical microscope (Keyence VHX-1000). The ×50 magnification was optimal to analyze the fibers and was mostly used in this study. Several samples were cut in the plates and mechanically polished for observation. The micrographs were numerically acquired and the fibers and matrix components were separated by simple thresholding, followed by the application of a watershed algorithm, using ImageJ [START_REF] Rasband | ImageJ software[END_REF].

X-ray Microscale

First change of scale based on 2D imaging

Knowledge of the detailed geometry and of the thermal properties of the components (fibers, matrix) of the composites is necessary to perform the first change of scale. For this, 2D micrographs taken perpendicularly to the yarn direction have been used. The assumption made is that the yarn is assumed to be unidirectional at this scale (i.e. the perpendicular pattern remains unchanged through the third direction). The parallel thermal conductivity (λ // ) is therefore simply obtained by a law of mixtures given by the following expression:

m m f f λ φ λ φ λ + = // (1)
where f φ and m φ are respectively the volume ratio of fibers and of the matrix in the material. f λ and m λ are respectively the conductivities of fibers and the matrix.

For the transverse conductivities, image analysis and computations are necessary.

The numerical procedure used is based on a change of scale procedure using the Volume Averaging Method. Starting from the equations at a given scale, this method leads to higher scale equations and closure problems allowing the determination of effective properties. The closure problem obtained for heat conduction is solved numerically with a homemade Finite Volume solver in a 1 voxel-thick 3D periodic unit cell representative of the studied medium, thus leading to the determination of the effective heat conductivity tensor [START_REF] Lux | Macroscopic thermal properties of real fibrous materials: Volume averaging method and 3D image analysis[END_REF]. For a given image, the fiber volume fraction is also assessed. The results are used to yield expressions relating the transverse and parallel conductivities to the local fiber volume fraction.

Second change of scale based on 3D µCT

The proposed procedure takes into account the true space distribution of phases and orientations, as sampled at the macroscale (see computation is carried out with the same numerical tool [START_REF] Lux | Macroscopic thermal properties of real fibrous materials: Volume averaging method and 3D image analysis[END_REF] as for the first one.

Results

Experimental

For each sample, the thermal field has been recorded as a function of time. From this thermal field evolution, it is possible to determine the thermal transverse diffusivity (averaged on composite thickness) for each pixel [21,22] (see Figure 3a,b) and to plot the thermal diffusivity histograms (Figure 3c). These maps and histograms demonstrate that, though both composites are quite similar in terms of thermal diffusivity magnitude, the chopped one displays more dispersion, as could be expected from its structure.

Moreover, thermal conductivities along transverse and longitudinal directions were measured by the hot disk method. These measurements only concern chopped composites and were done on 4 × 5 cm² samples. The results are in excellent agreement with those obtained through thermography, as can be seen in Table 2. Values are similar to those reported in [START_REF] Mottram | Thermal conductivity of fibre-phenolic resin composites. Part I. Thermal diffusivity measurements[END_REF].

Numerical results

As already mentioned, the method to calculate the equivalent conductivity tensor is based on 3D µCT images as input geometry of the material. But at the micro-scale, the resolution of µCT images was not sufficient, justifying the use of micrographs. We first present results on 2D micrographs for the first change of scale, and then on 3D µCT scans for the second change of scale.

First change of scale based on 2D imaging

The first change of scale has been performed on micrographs similar to the one presented in Figure 2d. Four of these images obtained after processing are presented on The results of effective conductivity computations were compared to known analytical estimations of the transverse conductivity proposed in the literature. First, the lowest conceivable bound is given by the harmonic average corresponding to the 1D law of conduction in series:

1 1 1 - - - ⊥ + = m m f f λ φ λ φ λ (2)
while the highest bound is given by the arithmetic average corresponding to the 1D law of conduction in parallel. A first more elaborate model has been proposed by Maxwell Garnett [START_REF] Garnett | Colors in metal glasses and in metallic films[END_REF], in which the thermal conductivity of a regular array of cylinders in a matrix is given as a function of fiber fraction by the following relationship:

m f m f f m m d d λ λ λ λ φ λ λ λ λ ) 1 ( ) 1 ( - + - = - + - ⊥ ⊥ (3)
where d is the dimension of the problem. This equation, with d =2, as is the case here, is

f m f f f f F F F F φ λ φ φ λ φ φ ⊥ = - + - - - (4)
and for a hexagonal array:

f m f f f f F F F F φ λ φ φ λ φ φ ⊥ = - + - - - (5) with m f m f F λ λ λ λ + = - .
+ + = ⊥ f f f φ φ φ λ (6)

Second change of scale based on 3D µCT

The second change of scale is performed on an image of a volume of the material large enough to contain an REV (Representative Elementary Volume). The image is divided into several sub-volumes (see Figure 5). For each sub-domain, the fibers and matrix are first thresholded to 50% black / 50% white, and anisotropy directions are then detected using a random walk algorithm where the walkers are only allowed to travel in one phase. This method, simulating a diffusion process in the image, is sensitive to its local structure. The analysis of eigenvectors and eigenvalues of the covariance tensor of the relative walkers' displacements gives the fiber direction in the sub-volume: the direction associated to the highest eigenvalue is the average fiber direction. This procedure has been successfully validated on µCT images of C/C composites [START_REF] Vignoles | Assessment of geometrical and transport properties of a fibrous C/C composite preform as digitized by X-ray computerized microtomography: Part II. Heat and gas transport properties[END_REF][START_REF] Coindreau | Assessment of structural and transport properties in fibrous C/C composite preforms as digitized by X-ray CMT. Part I : Image acquisition and geometrical properties[END_REF].

In addition to this, a correspondence between the average gray scale value of the subdomain and its local values of the fibers, pore, and matrix volume fractions is provided through the choice of correlation functions. As sketched in Figure 6, the gray scale histograms of the images can be modeled using two Gaussian functions: the first one corresponds to the inter-yarn material (i.e. principally matrix), the second one to the yarns themselves. The mode N2 of the first Gaussian corresponds to the matrix density and the mode N3 of the second one corresponds to the average density of yarns, i.e. of a material with fiber density corresponding to the volume fraction of fibers in the yarn, φ f,yarn , and matrix density corresponding to φ m, yarn = 1φ f,yarn , since there are no intrayarn pores. Between N2 and N3, a linear interpolation is made, and it is prolonged until the fiber volume fraction reaches 1. The pores are obtained by direct thresholding of the image, with a threshold value N1 chosen so that the experimental porosity is recovered. for the chopped composite.

Discussion

For both regular and chopped composites, the non-diagonal terms in the conductivity tensors reported in Eqs. ( 7) and ( 8) are negligible: directions x, y and z of the tomographic image match those of thermal conduction. Comparing with flash thermography results, for the regular composite, it can be noted that longitudinal conductivity (directions x and y with similar values) is, as in experiments, higher than the conductivity in the z direction. The agreement in both directions is excellent. The same tendency is obtained for the chopped composite. For this material, the computed λ * xx and λ * yy differ by 5%, indicating that the area selected for computation was somewhat too small with respect to an REV size. However, the computed value of transverse conductivity is, as in experiments, lower than longitudinal ones. The average computed longitudinal value matches the measured value within the error bounds.

The thermal anisotropy can be conveniently quantified by the following parameter:

// * * // * λ λ - λ = τ ⊥ (9)
Experimentally, we obtained anisotropies of 19.6%±7% and 13.7%±1% respectively for the regular and chopped composites, while the computations give values of 12% and 10% respectively, that is, somewhat too low, especially for the regular composite. Despite these remarks, the image-based computational procedure has shown its ability to successfully reproduce the effect of the reinforcement arrangement on heat conduction.

The numerical procedure has been repeated with small variations of the fiber and matrix conductivities, and of the grayscale levels used in the thresholding procedure, in order to obtain the respective normalized sensitivities 3. The sensitivity with respect to matrix or fibers conductivity lying respectively around 0.5 (matrix) and 0.7 (fiber), we conclude that a small error in the knowledge of these constituent properties has no catastrophic effect on the computational predictions (a 1% variation in λ m gives a 0.5% variation in λ * ). In the same manner, the threshold N1, though important for correct density determinations, has a very low impact on the effective conductivity. On the other hand, the method is more sensitive to the N2 and N3 levels chosen for the grayscale/density conversion function. A variation of 1 gray level of N2 or N3 implies a variation of about 1% in λ * . Since these parameters are obtained from the knowledge of the fiber and matrix volume fractions, the experimental determination of the latter quantities is the most critical point of the procedure.

Conclusion

This paper has presented a study of a silica/phenolic composite family based on two main approaches: (i) the measurement of thermal and structural properties through various experiments, and (ii) a double-step computational change of scale. The latter approach is based on 2D and 3D images of the microstructure of the composites. Using the properties of the constituents and their relative spatial organization, the approach yields effective conductivities of the composite.

The numerical results are in good agreement with experiments and can be easily applied to fiber-reinforced composites in general, using microscopic images and tomographic scans. Improvements are now necessary to optimize the change of scale routine calculation in terms of computational time.

The two composites with different spatial organizations have been found to have very close thermal conductivities in different directions. The transverse conductivities of the chopped composite display more dispersion on the plate, as expected from its structure. This may have a positive impact on ablation resistance; indeed, exposed to the same heat flux, the heat penetration depth will be more dispersed, resulting in a wavier pyrolysis front. The heat consumption by pyrolysis will therefore increase by the ratio of the actual surface to the projected surface, and will bring a better protection.

φφλλλλ

  value N2,N3 Gray scale values used for density/gray scale correspondence S xi Normalized sensitivity of λ * to the variation of x i Greek letters f Volume fraction of fibers φ f,yarn Volume fraction of fibers in a yarn m Volume fraction of the matrix φ m,yarn Volume fraction of the matrix in a yarn λ Thermal conductivity (Wm -1 K -1 )Local thermal conductivity tensor of a sub-block (Wm -1 K -1 )* Macroscopic thermal conductivity tensor of a composite (Wm -1 K -1 )f Thermal conductivity of the fibers (Wm -1 K -1 ) m Thermal conductivity of the matrix (Wm -1 K -1 )

  Computerized Tomographs (µCT) [16] were acquired using a laboratory device (Phoenics X-ray Nanotom) used in absorption mode with a resolution of 5 µm/pixel. The samples were extracted from the initial composite plate to be fully contained in the field of view at the resolution attempted. Reconstruction from the radiographs was performed by the standard filtered back-projection algorithm [17,18]. Examples of 3D µCT reconstructions are presented in Figure 1c,d.

[ 19 ]

 19 for details). The hypothesis made is that the phase distribution vs. property correlation is correctly sampled at the microscale and directly transposable for macroscale computations. The procedure consists in computing the effective thermal properties of the low-resolution images from a field of small-scale properties by the method of Volume Averaging. It starts with the subdivision of the low-resolution images into sub-images; then, inside every sub-image, an evaluation of fiber volume fraction and local fiber orientation is performed. This part of the algorithm is carried out by binarizing arbitrarily the image at 50% level threshold, letting random walkers run in one of the two phases, computing the variance of their centered displacements, and selecting the eigenvector associated to the highest eigenvalue (i. e. the direction of fastest diffusion). Once this has been done, local property tensors may be affected to every sub-image; the values of parallel and perpendicular conductivities come from the results of the first change of scale (see above), as a function of the local grayscale level and the tensors are properly rotated to be expressed in the axes of the sample image considered. Finally a change of scale

Figure 4 .

 4 Figure 4.

  equivalent to the relation of Hasselman & Johnson [25]. More elaborate relations were proposed by Perrins et al. [26] for a square array of cylindrical fibers:

  Using this information and the correlations obtained from the first change of scale, longitudinal and transverse thermal conductivities are computed. For each sub-volume, a diagonal thermal conductivity tensor is allocated in its own principal directions then rotated back in the image's global frame [19]. The effective macroscopic conductivity tensor is then obtained from the data of all sub-domains by solving the closure problem associated to the Volume Averaging Method, using the same solver as for the first change of scale [20].Macroscopic conductivity tensors, λ * , for both composites, obtained thanks to this double change of scale method, on the 3D blocks shown in Figure1c,d,

  1,2 or 3), as reported in Table

Figure 1 -

 1 Figure 1 -Photographs of the studied materials: a,c) regular composite; b,d) chopped

Figure 2 -

 2 Figure 2 -Scale heterogeneity evidences with a) macroscopic, b,c) mesoscopic and d)

Figure 3 -

 3 Figure 3 -Heat diffusivity maps from the flash experiments on a) plain woven

Figure 4 -

 4 Figure 4 -Transverse conductivity vs. fiber ratio calculated by change of scale

Figure 5 -

 5 Figure 5 --Illustration of the computations for each subdomain prior to the second

Figure 6 -

 6 Figure 6 -Above: histogram of the original image, with two fitted Gaussians, one

Figure 2 .

 2 Figure 2.

Figure 4 .Figure 2 .Figure 5 .

 425 Figure 4.

  The comparison of the transverse conductivity vs. fiber ratio curves calculated with all these laws and the one obtained by fitting the numerical results is reported in Figure 4. It can be seen that the relationships of Maxwell Garnett and of Perrins et al. always underestimate slightly (by 5% or less) the computed values. At high fiber volume fractions, the law of Perrins et al. for square arrays of cylinders matches well the numerical data. For the sake of convenience, the transverse

	conductivity ⊥ λ has been fitted by the following polynomial law:
	-2.021932	3	4.627975	2	-	2.202157	0.7120661

Table 3 -

 3 Normalized sensitivities of the computed macroscopic thermal conductivities to different parameters COLOR FIGURES (WEB VERSION ONLY)

	Normalized	Regular	Chopped
	sensitivities	Longitudinal	Transverse	Longitudinal	Transverse
	to :
	λ f	0.70	0.64	0.68	0.61
	λ m	0.50	0.55	0.52	0.56
	Ν1	0.12%	0.13%	0.11%	0.13%
	Ν2	0.9%	1.0%	0.9%	1.0%
	Ν3	0.9%	1.0%	0.9%	1.0%

! Figure 1.

Acknowledgements

GIS "Advanced Materials in Aquitaine" is acknowledged for a 1-year post-doc grant to G. B. The authors would like to thank R. Huillery (Fahrenheit) for the hot disc experiments; R. C. Oliveira da Rosa & V.-E. Renaud (Arts et Métiers ParisTech -Bordeaux) for density measurements and help for tomographic acquisition; G. Caillard & V. Rolland de Chambaudoin d'Erceville (Arts et Métiers ParisTech -Bordeaux) for taking micrographs and running the change of scale software; A. Chirazi (Tomomat -Bordeaux) for help in acquiring the tomographs.

Quantity Fibers Matrix

Density (g.cm -3 ) 2.21 ± 0.01 1. [START_REF] Garnett | Colors in metal glasses and in metallic films[END_REF]