Christian Doerr

Siyu Tang

Norbert Blenn

Piet Van Mieghem
email: vanmieghem@tudelft.nl

{c Doerr

Are Friends Overrated? A Study for the Social Aggregator Digg.com

de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

The recent explosive growth of online social network (OSN) platforms such as Facebook, Twitter, or Digg has sparked a significant interest. As several hundred millions users now regularly frequent these sites to gather and exchange ideas, researchers have begun to use this comprehensive record to analyze how these networks grow by friendship relations, how information is propagated, and who are the most influential users. A good understanding of these principles would have many applications, such as effective viral marketing [START_REF] Richardson | Mining knowledge-sharing sites for viral marketing[END_REF], targeted advertising [START_REF] Yang | Mining social networks for targeted advertising[END_REF], the prediction of trends [START_REF] Surowieck | The Wisdom of Crowds[END_REF] or the discovery of opinion leaders [START_REF] Davitz | ilink: search and routing in social networks[END_REF].

A fundamental assumption of previous research is that friendship relations are a critical component for the proper functioning of social networks [START_REF] Boyd | Social network sites: Definition, history, and scholarship[END_REF], i.e., they assume that information, opinions and influences are sourced by single individuals and then propagated and passed on along the social links between members. The extent, density, layout and quality of the social links and the network of links will therefore determine how information can be spread effectively.

In this paper, we report on results from a multi-year empirical study of the OSN Digg.com, a so-called social news aggregator, that indicate that the criticality and importance of individual friendship relations and the friendship network is less than previously perceived. In these social news aggregators, users submit news items (referred to as "stories"), communicate with peers through direct messages and comments, and collaboratively select and rate submitted stories to get to a real-time compilation of what is currently perceived as "hot" and popular on the Internet. Yet, despite the many means to communicate, interact and spread information, an analysis of eleven million stories and the commenting and voting patterns of two million users revealed that the impact of the friendship relations on the overall functioning of the social network is actually surprisingly low. In particular, we find that, while users indeed form friendship relations according to common interests and physical proximity, these friendship links are only activated in 2% of the information propagation. Furthermore, in 50% of all stories that became "hot", there was no sufficient prior contribution by the friend network to trigger the popularity of the story. Instead, we find that a critical mass was reached through participation through random spectators.

The remainder of this paper is structured as follows: Section 2 discusses related work and prior findings on the role and characteristics of friendship links and the friendship network in OSNs. Section 3 describes background information about the social network used in our experimentation and our data collection methodology. Sections 4 and 5 discusses the role of friendships and selected individuals to the successful information propagation. Section 6 present an outlook on the issue of time dependencies in Digg. Section 7 summarizes our findings.

Related Work

Ever since the publication of Katz and Lazarfeld's argument for the origin and spread of influence through communities [START_REF] Katz | Personal Influence[END_REF], researchers have investigated the mechanisms by which ideas and opinions are passed along social relationships. The wide-spread popularity of OSNs now provides an easily accessible, machinereadable data source for broad-scale analysis. As it is commonly assumed that friendship interactions are the backbone of social networking platforms [START_REF] Boyd | Social network sites: Definition, history, and scholarship[END_REF] along which a "web of influence" [START_REF] Koller | Representation, reasoning and learning[END_REF] is extended and maintained, the investigation of how links are formed and used has received significant attention.

The mechanisms by which these social ties are formed is still subject to investigation. Fono and Raynes-Goldie [START_REF] Fono | Hyperfriends and beyond: Friendship and social norms on livejournal[END_REF] for example studied the semantics of friendship relations in the OSN LiveJournal and find that a number of overlapping processes drive the formation of links: ties may be formed as measures of trust, reciprocity, an extension of offline acquaintance or as a facilitator for information transmission. This function of friends as content providers [START_REF] Raynes-Goldie | Pulling sense out of today's informational chaos: Livejournal as a site of knowledge creation and sharing[END_REF] is a strong force, as it even drives the friend selection of users: in a usage survey on Facebook, subscribers named their interest to obtain information from friends to form friendship relations [START_REF] Ellison | The benefits of facebook "friends:" social capital and college students' use of online social network sites[END_REF]. According to network theory, such content dissemination should work best across "weak ties" [START_REF] Granovetter | The strength of weak ties[END_REF] which are linking tightly connected clusters, as these should transmit information with the least amount of redundancy. Therefore, the predominant share of OSN research has been conducted to investigate the topological properties of OSN and to understand how users behave and exchange content and information across their social links.

Along these lines, Mislove et al. [START_REF] Mislove | Measurement and analysis of online social networks[END_REF] studied the topological properties of four OSNs at large-scale: Flickr, YouTube, Live-Journal, and Orkut, for which they evaluated different network metrics, e.g. link symmetry, node degree, assortativity and clustering coefficient. The OSNs were characterized by a high fraction of symmetric links, and contained a large number of highly connected clusters, indicating tight and close (transitive) relationships. The degree distributions in the OSNs followed a power-law with similar coefficients for in-and out-degree, showing the mixed importance of nodes in the network -there are few well connected and important hubs to which the majority of users reach to.

In [START_REF] Leskovec | Planetary-scale views on a large instant-messaging network[END_REF], Leskovec et al. presented an extensive analysis about communication behaviors of the Microsoft Messenger instant-messaging users. The results of 30 billion conversations among 240 million people showed that people with similar characteristics (e.g., age, language, and geographical location) tend to communicate more. Structurally, in terms of node degree, cluster coefficient, and shortest path length, it was shown that the communication graph is well connected, robust against node removal, and exhibits the small-world property.

Another line of research aims to discover factors for content popularity and propagation in OSNs. For instance, it is shown in [START_REF] Cha | A measurement-driven analysis of information propagation in the flickr social network[END_REF] that there are different photo propagation patterns in Flickr and photo popularity may increase steadily over years. A similar study was performed with YouTube and Daum in [START_REF] Cha | Analyzing the video popularity characteristics of large-scale user generated content systems[END_REF]. Here, video popularity is mostly determined at the early stage after content submission. Such observations are also voiced in the viral marketing literature where it is assumed that "few important trends reach the mainstream without passing the Influentials in the early stages, ... they give the thumbs-up that propel a trend". [16, p. 22]. As it is however quite difficult to evaluate concretely and at a population scale how content is disseminated, there exists to this date no population-level (on the order of millions of users thereby also considering possible emergent properties) evaluation of these hypotheses.

This paper aims to address this void, and from this current state of research, we therefore formulate two hypotheses that will be addressed and investigated for the scope of an entire social network: H 1 There exist critical members inside the community who have better or earlier access to important information.

H 2 Inter-personal relations and the overall network of friendships are the key component to the successful spread of information.

3 The "Digg" data collection description of the content. New submissions gets enqueued to the upcoming pages where they are staying for a maximum of 24h. Users may explore the upcoming section by topic or a recommendation system, which displays stories that already gained attention and votes. A secret algorithm by digg.com chooses stories from the upcoming section to promote them to the front pages which is the default page when entering the Digg website. After this promotion a story will therefore obtain a lot of attention.

Within the Digg network, it is possible for users to create friendship connections to other users. One may either be a fan or a mutual friend to another person. Fans and friends are notified by the friends interface of Digg if their friend has "digged" or submitted a story. 1 We studied different aspects of Digg, such as the friendships, user characteristics and activities, and the properties and dynamics of the published content. While most social network traces are crawled using friendship relations, e.g. [START_REF] Mislove | Measurement and analysis of online social networks[END_REF] and [START_REF] Ahn | Analysis of topological characteristics of huge online social networking services[END_REF], the Digg dataset was obtained by a simultaneous exploration from four different perspectives, as shown in Fig. 1:

Site perspective: The Digg website lists popular and upcoming stories in different topic areas. Peridiocally all front pages with all popular stories and all upcoming stories were collected. All discovered stories are added to an "allknown story" list maintained by us.

Story perspective: For all stories, a complete list of all diggs performed by users is collected. Newly discovered users will be added for future exploration.

User Perspective: For each discovered user, a list of their previous activities is obtained. If new stories are found the entire activities is retrieved.

Social Network Perspective:

A list of friends is downloaded for every user. If a user is newly found, he is added to the data discovery process, and a list of all friends and user profile information are fetched.

The above procedure is continued until no new user and story can be found and periodically repeated afterwards to discover new activity. By using the above crawling methodology, we are able to collect (nearly) the entire information about friendships, activities of users and the published content in the Digg network. This is important as traditional crawling techniques will only discover those users which are linked within the social network and will overlook for example all users without any friendship relations who are still otherwise active members. In our case our crawling technique discovered nearly twice as many users than could have been identified by a pure crawl of the social network alone. This outcome might (partially) explain some of the contrary findings in our paper. Our data covers the entire span since the beginning of Digg in 2004 until the end of our study in July 2010 and contains a volume of more than 600 GB, covering the history of 2.2 million registered users and 11 million stories.

Information Spread through the Network of Friends

As discussed in the introduction, it is commonly assumed that the friendship relations within a social network are a critical components to the successful spread of information. This section will dissect this process and investigate for the case of the Digg OSN, whether the propagation of news is indeed the results of the activation of users' ties.

Self-Organization of the Friendship Network

According to sociological theory, friendship relations in an OSN grow directed by common interests and tastes [START_REF] Raynes-Goldie | Pulling sense out of today's informational chaos: Livejournal as a site of knowledge creation and sharing[END_REF]. Within Digg, all news stories are classified within eight major topic areas, subdivided by 50 special interests. When matching the users' concrete digging behavior with the topic area into which a story was classified, we find that the subscribers exhibit quite strong and distinct preferences and tastes for individual topic areas. As shown in Fig. 2, if a particular user reads, diggs and is therefore interested in two distinct topic areas, say for example "Science" and "Technology", more than 70% of all consumed stories fall within the most preferred genre. For three topic areas, the favorite one draws 65%, and even for users interested in all eight categories the top two will on average still account for 60% of read stories. These rankings of user interest provide a direct measure of how similar the tastes and preferences of users in their information acquisition are. When comparing two users and their ranking of topics, we use the number and distance of permutation steps required to transform one list into the other (the Waserstein rank distance [START_REF] Rüschendorf | The wasserstein distance and approximation theorems[END_REF]) as a measure of user similarity. A network-wide analysis of the similarities between friends shows that users directly connected to each other have a very high alignment of their preferences and tastes: 36% of rank lists are identical, 20% require one transformation, and within three transformation steps 80% of all friendship relations are aligned.

While there exists a perfect overlap between the interests and tastes of friends, there is a surprisingly low amount of common activity among friends Fraction of digged stories and only 2% of all friend pairs actually do digg on the same story. The hypothesis that common interests result in the formation of friendships in order to gain information from neighboring peers [START_REF] Fono | Hyperfriends and beyond: Friendship and social norms on livejournal[END_REF] would also predict that the more similar the tastes between friends are, the closer the alignment of clicking patterns would be. In practice however, we found this not to be the case.

Number of interested topics

n k = 1 k = 2 k = 3 k = 4 k = 5 k = 6 k = 7 k = 8
Yet, pairs of friends do not exist in isolation, but are embedded within a larger network of the friends of the friends. This in OSNs very dense network of friends [START_REF] Mislove | Measurement and analysis of online social networks[END_REF] may be a powerful promoter, as theoretically a large group can be reached if information can be passed on from friend to friend over several steps.

Our analysis shows that information can indeed travel over multiple hops from the original submitter (see Fig. 3(a)) and on average does reach 3.7 hops from the source until the propagation dies down. The actual contribution of the multi-hop network, i.e., the number of friends of friends that can be activated, is however rather limited. As shown in Fig. 3(b) nearly 70% of the ultimately participating network of friends consists of the submitter's direct friends, while the benefit of the additional hops decreases super-exponentially. This result is not astonishing given the generally low activation ratios of friends and possible redundancies in the spread as indicated by the dashed line in figure 3(a).

Reaching Critical Momentum

All news stories submitted to Digg are initially collected in the "upcoming" list, which with more than 20 000 submissions a day has a very high turnover rate (more than 800/h). In order to become promoted to the front pages, a story has to attract sufficient interest, i.e., a large enough number of diggs, within 24 hours, which as shown in Fig. 4 the majority reaches within 16 hours. We experimentally determined that about 7 diggs/h are necessary to qualify for the promotion, thereby stories should gather on average around 112 diggs.

A story can rally this support initially from random spectators or friends of the submitter, who were notified about the newly placed story. Figure 5 shows the probability that a given number of friends is active on the website on the same day, and we compute the likelihood that at least 112 friends are online within 24 hours to be about 0.01. This expectation corresponds with the actually observed promotion success ratio. The fine line between failure and success, whether a story will be forgotten or becomes popular, therefore strongly depends on the underlying stochastic process, whether at a certain time a sufficient number of friends are online to support the story. In the remaining 99% of the cases when not enough friends are online, additional support needs to be rallied from users outside the friend network to reach the promotion threshold.

Promotion without Friendships

As the likelihood that a story becomes popular solely through the submitter's friendship network is rather slim (given the low activation ratio of friends, the limited contribution of the network of friends and the low probability of a critical mass of friends active on the same day), in most cases the contribution of nonfriends is necessary to push a story up to the promotion threshold.

Table 1 shows the ratio of friends and non-friends active on a story both before and after the promotion for all stories that became popular within the Digg network. Here, two distinct groups emerge. In about 54% of all cases, a story was marketed predominantly by friends, although a contribution of non-friends (28%) was necessary for the story to reach critical mass. Figure 6(a) shows this aggregated pattern for an example story in this class. In the remaining cases (46%), stories were spread and digged predominantly by users outside the submitter's friendship network. Figure 6(b) shows a typical example for this pattern. Once the promotion threshold is crossed, both types of stories are read more by non-friends, as the quantity is usually significantly larger and the contribution of the submitter's friendship network may already be exhausted.

The Criticality of Individuals

The successful spread of information cannot be explained directly from the social ties inside our investigated online social network, neither through the relationships among individual friends nor from the usage and outreach of users into their friendship network. This naturally raises the question whether all users are equal inside the network, or whether there are some individuals in the social community (a) who themselves have better (or earlier) access to important content and are therefore able to get a high number of popular stories, (b) can use the friendship network more efficiently, act as motivators able to overproportionally recruit friends, or (c) able to early on spot content that will later resonate with the masses and become a hit. These questions will be the focus of this section.

There exist a number of ways to define the importance or criticality of individuals in networks. In complex network theory and social network analysis, importance is typically defined from a structural perspective, using topological metrics such as node degree or betweenness [START_REF] Scott | Social Network Analysis: A Handbook[END_REF], which measure how well a particular node is connected to its surrounding peers and how many possible communication paths between nodes in the network will traverse this node. Using this definition of importance, most studies of online social networks find a small number of topologically critical nodes [START_REF] Mislove | Measurement and analysis of online social networks[END_REF][START_REF] Benevenuto | Characterizing user behavior in online social networks[END_REF][START_REF] Leskovec | Planetary-scale views on a large instant-messaging network[END_REF], resulting from the power-law degree distribution of these complex networks: there exist a few well-connected nodes with whom a large number of users are friends. In our analysis, we confirm these findings and will (for now) use this definition of critical individuals.

Contrary to other OSNs however, we do not only observe a skewed distribution in the degree and connectivity of nodes, but also in the symmetry of relationships among users. While most OSNs show high levels of link symmetry, for example 74% of links in LiveJournal and 79% of links in YouTube are found to be bi-directional [START_REF] Mislove | Measurement and analysis of online social networks[END_REF] average) and also vary with the degree of the node: the more connections an individual B already has, the less likely it is to match an incoming new friendship request from A. In Digg, A thus becomes a "fan" of B, thereby receiving notifications about the activities of B, but not vice versa. This observation of decreasing reciprocity is consistent with sociological theory and ethnographic studies of social networks which showed that friendship requests in OSNs are often driven by users' interests to become passively informed by means of these social ties [START_REF] Fono | Hyperfriends and beyond: Friendship and social norms on livejournal[END_REF][START_REF] Ellison | The benefits of facebook "friends:" social capital and college students' use of online social network sites[END_REF]. The fact that the average symmetry is significantly lower and also dependent on the degrees of remote nodes, underlines (a) that users are engaging in friendships in Digg with the intention of information delivery and (b) the existence of individuals which act (or view themselves) as sources and broadcasters of knowledge, which according to [START_REF] Keller | The Influentials: One American in Ten Tells the Other Nine How to Vote, Where to Eat, and what to Buy[END_REF] would embody the critical influentials in the network.

Submitting Successful Stories

When looking at all stories submitted in the past 4 years, we indeed find that users are very different when it comes to generating and sourcing important information. While the content published on Digg is followed about 25 million visitors a month, only a limited number of registered users are actively submitting content. The activity patterns of these users is furthermore biased, as shown in the Lorentz curve [START_REF] Lorentz | Methods of measuring the concentration of wealth[END_REF] in Fig. 7: the 80% least active users of the network are together submitting only about 20% of the entire content as indicated by the dashed red line. While this is far from an equitable system, the same skewcommonly referred to as the 80-20 or Pareto rule -has been found repeatedly in economics and sociology. Here it is however more drastic when only considering those stories that gained enough support and were promoted to popular. As the figure shows, these successful stories can be attributed to a selected minority of 2% of the community, which is able to find and submit 98% of all stories. This effect is however not the result of the pure quantity. In other words, there exists no statistically significant relationship between the number of stories a person has submitted and the ratio of stories that will become popular (Pearson's correlation coefficient r 2 =-0.01). While the presence of such a highly skewed distribution seems to suggest the existence of a few "chosen ones", a closer inspection reveals that these highly successful submitters are also not those users responsible for the effective spread of information. First of all, the average ratio of popular to submitted stories of the top 2% successful submitters is only 0.23. Second, the group of users who rank among the top successful members of the community is highly volatile, and the set of successful users changes substantially between studied time intervals. As we do not find a significant number of members who are able to continuously repeat their previous successes, we may conclude that there exists no conceptual difference or strategic advantage with those who do score successful stories. It appears that they were simply in the right place at the right time.

In conclusion, it is not predominantly the well-connected nodes that are the originator of wide-spreading content, as there is no significant relationship between a user's success ratio and its degree with those around it (p-value>0.5).

Activation of the Social Network

While there do not exist any particular nodes that are overly successful in injecting content, it may be possible that there exist users highly successful in activating their friendship network, and therefore would be a key component in helping stories reach widespread popularity.

It turns out that the activation ratio of a node's direct friends is surprisingly low. On average, a particular node is only able to generate 0.0069 clicks per friendship link. This recruitment is furthermore quite stable with the structural properties of the network nodes. While the literature predicts that nodes in a social network achieve an exponentially increasing influence compared to their importance [16, p. 124], we find a linear relationship (r 2 =0.76) between the size of a nodes' friendship network and the amount of users it can recruit to click on a story. As the slope of the linear regression is low (a=0.102), there is no overproportional impact of higher-degree nodes: 1 activated user with 100 friends is on average about as effective as 10 activated users with 10 friends.

While we find no quantitative difference in the friendship network around the important nodes, there may be a qualitative difference in terms of structural characteristics and the information propagation along links. As complex networks evolve, certain growth processes such as preferential attachment [START_REF] Simon | On a class of skew distribution functions[END_REF] create sets of highly connected clusters, which are interconnected by fewer links. According to social network theory [START_REF] Granovetter | The strength of weak ties[END_REF][START_REF] Csermely | Weak Links: Stabilizers of Complex Systems from Proteins to Social Networks[END_REF], these links among clusters, commonly referred to as "weak ties", act as a critical backbone for information propagation. Information within a cluster is communicated and replicated between nodes thereby creating high redundancy, while the weak ties transport other, previously unknown information between groups of nodes (see Fig. 9(a)).

To evaluate this hypothesis, we classified the network into weak and strong ties according to their edge betweenness and compared their theoretical importance to the actual amount of content that was propagated between each pair of nodes. information conductivity, demonstrating that the distributions are in general comparable. As there is no hard threshold for what characterizes a weak or strong tie, we compared the top and bottom 20% of the distribution as weak and strong ties respectively to the amount of stories propagated along a certain link. As shown in Fig. 9(c), there exists no relationship (r 2 = 0.00006), thus information is not propagated more effectively along weak ties.

Early Predictors

Finally, we investigated if there exist certain individuals who might be called important and influential in the sense that they are able to early-on identify content that will later on become popular (see for example [START_REF] Keller | The Influentials: One American in Ten Tells the Other Nine How to Vote, Where to Eat, and what to Buy[END_REF]). In the months of April-May 2009, we followed the voting patterns of all registered users on all stories to determine how successful users were in finding and clicking on content that within the next hours or days would become popular. Of all activity within this two month time period, users identified and reacted on average only to 11.9% of content before it got promoted. With the absence of any high performers, there are thus no specific individuals who are able to consistently and repeatedly find emergent trends. This observation did not change either for the case of the high degree individuals or the users with a high success ratio of submitting successful stories; there exists no statistically significant difference in their ability to find content in the social network before it actually reaches widespread popularity.

6 Beyond Pure Friend Relations

The discussions in section 4 and 5 show that neither the importance of individual users nor the dynamics of the individual friendship relations or the network of friends can solely explain if a certain story will become a success. Furthermore, as in nearly 50% of all stories the promotion process took place without any dominant contribution by the friendship network, we further investigated how the low participation values of the friendship network may be explained and which features are the dividing force between those stories pushed by friends and those promoted by the general public.

Spread Without Friends -A Matter of Timely Relevance

To investigate why one story is propagated by friends while another one is pushed by random users, we conducted a controlled experiment and presented the 158 most successful stories in the last year to a group of non-experts. In the experiment, stories were displayed to participants using the same user interface as on digg.com, except that only one story was displayed at a time to eliminate distractions. As we could in retrospect classify these stories as promoted by friends or non-friends, the stories in the experiment were balanced in terms of topic areas and to mimic a similar distribution as on Digg. Looking at the title, description, link, digg count and if available preview image, we asked participants to rate each story in terms of general appeal, their own personal interest and the general importance of a particular story.

From the experiment it became evident that the difference between friends and non-friends promotion was a direct result how important and relevant the participants rated a particular story. Whenever participants marked a story as being "of general interest to the public", in other words it is likely that one would hear it in the evening news, or attributed it with a high level of timely relevance, the same story has also reached popularity on Digg by non-friends. Thus, whether stories will become friend or non-friend promoted seems to be a function of a stories' content and appeal (both stat. significant at p=0.05).

Explaining Critical Mass Through Temporal Alignment

As a large number of factors previously assumed to be of importance to information spread turned out in our study of Digg to be rather insignificant and highly volatile over time, we further investigated the influence of time on the story propagation process. We found that some of the unexpected low or highly fluctuating factors are to some extent dependent upon the temporal alignment of users, i.e., whether users in general (and friends in particular) are visiting the site within the same narrow time window or not.

Figure 10 visualizes this idea of temporal alignment on a snapshot of the front pages from April 2009, which shows the position of all popular stories with at least 100 diggs over a 48 hour time interval on the first 50 front pages. There exists a high flux in the amount of stories passing through as within on average 3 hours the entire content on the first front page has been replaced by newer items. From a combined analysis of voting patterns and front page traces, we are able to determine the usual search strategy and search depth of users on Digg. Stories accumulate 80% of their attention received after promotion on the first and second page only, while the ratio of users who are scanning more than the first 4 front pages is practically zero.

Considering the case of two users active on 20.4.2009, this can explain the surprisingly low amount of common friendship activations, as nearly 70% of the stories visible to user A during the two morning visits are already outside of user B's attention window as the user visits the site just six hours later. Unless B actively looks for and follows up on A activity, the abundance of content and high turnover rate of information combined with limited attention span will therefore largely limit the potential for commonality. This demonstrates that whether a story reaches critical mass depends to a significant amount upon who and how many people are currently active on the site within a short time window.

A combination of this temporal perspective with interest and friendship data can go a long way and provide a much more detailed understanding of user behavior, as we were able to improve our analysis accuracy of the activation ratio of friendship links by a factor of 15. Note however that while a temporal view is currently able to reveal in retrospect why certain users clicked on a particular story, it is not yet possible to predict how users will interact on a story in the future for a variety of reasons. Most importantly, an accurate prediction will require a good model of users' future activity periods at a fine enough resolution to minimize the prediction error of which stories users will see. Furthermore, it will be necessary to further understand the concrete decision process that will lead to a users actively clicking on a story.

Conclusion

In this paper, we have evaluated the assumption made in OSNs that friendship relations are the critical factor for information propagation. While we find evidence that friendships are formed based on common interests, the actual effectiveness is surprising low and does not confirm the high importance attributed to them -at least in digg.com. We furthermore notice that although there exists a significant skew in the characteristics of network nodes from a topological perspective, we do not find any evidence that some users are more effective in terms of spreading information. They have no better access to information, are not more efficient in triggering their friends nor do predict trends better. Vari-ous outcomes of our analysis point to a factor that in the past has not received sufficient attention: time period overlaps. We find that when incorporating this factor, the conductivity of friendships and our ability to explain the spread of information improves manyfold. This will be the focus of future research.

Fig. 1 .

 1 Fig. 1. Different components of the Digg crawling process.

Fig. 2 .

 2 Fig. 2. The average ratio of the k-th favorite topic of users that are interested in n topics after ranking.

Fig. 3 .

 3 Fig. 3. Most of the entire friendship network spreading out from the submitter is actually already covered by the first hop.

Fig. 4 .

 4 Fig. 4. Stories have to gain enough momentum within 24h to be promoted to the front pages.

  friends at the same day

Fig. 5 .Fig. 6 .

 56 Fig.5. The probability for a given number of friends to be active within 24h decreases rapidly.

Figure 9 (Fig. 9 .

 99 Fig. 9. While according to the weak ties hypothesis, (fig. a) the links connecting different clusters and communities (high edge betweenness) are critical to the spread of information and the topology and usage patterns of the social network showed similar network characteristics (e.g. the weight/degree distribution in fig. b), there existed no relationship between the strength of the tie and the amount of information propagated, neither for the entire network nor for the subclasses of strong and weak links (fig. c).

Fig. 10 .

 10 Fig.10. The high turnover rate of even the popular stories and the limited attention span and activity period of users can offer an explanation of the low importance of friendships. The intensity of a line indicates the rate of diggs a story is accumulating.

Table 1 .

 1 Ratio of friends/non-friends among the number of diggs for popular stories

	Before popular	After popular
	Average ratio Friends Non-friends Friends Non-friends
	a) 63484 stories 0.72	0.28	0.25	0.75
	b) 51679 stories 0.23	0.77	0.14	0.86

  , the relationships in Digg are less reciprocative (38% on

		1
		0.8
	ratio of stories	0.2 0.4 0.6			Li ne of Eq ua lit y Sto ries (gin i coe ff=0 .48)			Degree [0, 10) [10, 100)	# Users Sym. link 282536 0.53 49416 0.42
		0			Popular Stories (gini coeff=0.992)		[100, 1000) 13993	0.39
		0	0.2	0.4	0.6 ratio of users	0.8	1	1000	111	0.31
	Fig. 7. While a significant share of users submit stories into the system, only the stories of a selected few are reaching critical mass to become popular.	Fig. 8. Fraction of sym-metric links in the Digg network

It should be noted at this point that the semantics of a friend in Digg (obtaining information) is certainly different from a friendship in Facebook (personal acquaintance) or LinkedIn (business contact)[START_REF] Raynes-Goldie | Pulling sense out of today's informational chaos: Livejournal as a site of knowledge creation and sharing[END_REF], as also the main function differs between these social networks. As this paper investigates information propagation and social news aggregators such as digg.com focus on the exchange of information, these results are only immediately applicable to this type of OSN. To what extent these findings can be extended towards other types needs more investigation.


Enrico Gregori

Alessandro Improta
email: l.lenzini|alessandro.improta@iet.unipi.it

Luciano Lenzini

Lorenzo Rossi

Luca Sani
email: luca.sani@imtlucca.it

BGP and Inter-AS Economic Relationships

Keywords: BGP, Internet, Autonomous System, Tagging algorithm, Inter-AS Economics

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction and Related Work

The Internet is a collection of Autonomous Systems ASes 4 (ASes) connected to each other via Border Gateway Protocol (BGP) on the basis of economic contracts that regulate the traffic exchanged between them. The real structure of the Internet is still unknown, since there are neither standard methods nor dedicated tools to retrieve the needed information from the Internet itself. Researchers have tried to retrieve this topology using existing tools (e.g. traceroute) and by exploiting BGP information obtained from projects that deployed several monitors in significant locations (e.g. on IXPs) across the world. Typically, the Internet is studied as a graph in which nodes are ASes and edges are BGP connections between them, for example see [START_REF] Gao | On inferring autonomous system relationships in the internet[END_REF][START_REF] Oliveira | Quantifying the completeness of the observed internet as-level structure[END_REF][START_REF] He | Lord of the links: A framework for discovering missing links in the internet topology[END_REF][START_REF] Gregori | The impact of ixps on the as-level topology structure of the internet[END_REF]. A particular area of interest is the discovery of economic relationship among ASes.

The undirected graph of the Internet is not sufficient to determine the real importance of each AS since it is not possible to deduce all the possible sequences of ASes that packets can traverse. Contractual agreements could override scientific metrics (e.g. the length of the AS path [START_REF] Gao | The extent of as path inflation by routing policies[END_REF]), thus some of the paths that can be extracted using the undirected graph might not actually be used in the real Internet even though we know each of the connections that make up that path.

Given the heterogeneity of the ASes that form the Internet (e.g. ISPs, CDNs, universities, research networks, factories), AS relationships are fundamental to determine routing policies that will select allowed paths over which inter-AS traffic can flow. The availability of a topology of the Internet that would be aware of the economic relationships among each AS has several practical implications in the real world. For example, a CDN could use this knowledge to select the best places in which to deploy replicas of its server, and a new regional ISP could select the best upstream ASes through which it could connect to the rest of the Internet [START_REF] Subramanian | Characterizing the internet hierarchy from multiple vantage points[END_REF]. AS relationships are also important to yield a better insight into the business choices that led to the creation of the current Internet structure. In the literature, economic relationships between ASes are usually classified into customer-to-provider (c2p), provider-to-customer (p2c), peer-to-peer (p2p) and sibling-to-sibling (s2s) [START_REF] Huston | Interconnection, peering, and settlements[END_REF][START_REF] Gao | On inferring autonomous system relationships in the internet[END_REF]. In c2p and p2c, an AS (customer) pays another AS (provider) to obtain connectivity to the rest of the Internet. In p2p, a pair of ASes (peers) agree to exchange traffic between their respective customers, typically free of charge. In s2s agreement a pair of ASes (siblings) provide each other with connectivity to the rest of the Internet.

The first work on tagging the Internet AS-level topology was [START_REF] Gao | On inferring autonomous system relationships in the internet[END_REF], which proposed applying a heuristic on public BGP routing information to infer economic relationships between ASes. The heuristic was based on the fact that routes that two ASes exchange must reflect the economic relationship between them, and that a provider typically has a larger node degree5 than its customers, while two peers typically have comparable degree. In [START_REF] Gao | On inferring autonomous system relationships in the internet[END_REF] it was also proved that if all ASes respect the export policies imposed by such economic relationships, then the AS path in any BGP routing table must be valley-free, i.e. after traversing a p2c or p2p, the AS path cannot traverse a c2p or p2p. Later, [START_REF] Subramanian | Characterizing the internet hierarchy from multiple vantage points[END_REF] formulated the problem of assigning a tag to each connection as an optimization problem, the Type of Relationships (ToR) problem, using the number of valley-free paths as an objective function and proposed a heuristic to solve it. The ToR problem has been proven to be NP-complete [START_REF] Battista | Computing the types of the relationships between autonomous systems[END_REF][START_REF] Erlebach | Classifying customer-provider relationships in the internet[END_REF], thus several authors have proposed different heuristics and enhancements to resolve it, for example [START_REF] Battista | Computing the types of the relationships between autonomous systems[END_REF][START_REF] Erlebach | Classifying customer-provider relationships in the internet[END_REF][START_REF] Dimitropoulos | Inferring AS relationships: dead end or lively beginning? 4th Workshop on Efficient and Experimental Algorithms[END_REF][START_REF] Kosub | Acyclic type-of-relationship problems on the internet[END_REF].

Other interesting approaches in the tagging issue were developed in [START_REF] Xia | On the evaluation of as relationship inferences[END_REF] and in [START_REF] Oliveira | Quantifying the completeness of the observed internet as-level structure[END_REF]. The algorithm proposed in [START_REF] Xia | On the evaluation of as relationship inferences[END_REF] started from a partial set of information about the relationships between ASes, inferred using the BGP COMMUNITY attribute and from a set of information gathered through the IRR databases in order to obtain an entire set of AS relationships. However there is not a standard in using the BGP COMMUNITY attribute that could lead to a systematic method to extract useful information, and data available in IRRs have no guarantees regarding completeness and freshness. The algorithm proposed in [START_REF] Oliveira | Quantifying the completeness of the observed internet as-level structure[END_REF] was based on the fact that BGP monitors at the top of the routing hierarchy, i.e. monitors at Tier-1 ASes, are able to reveal all the downstream p2c over time, assuming that routes follow a no-valley policy. Considering the large number of variables that could affect AS commercial agreements and the entropy that is present in the BGP data, we believe that the no-valley approach itself could lead to inaccurate results. In this work, we introduce another kind of approach to this problem. In order to distinguish paths that can lead to correct economic tags from those that merely introduce noise, we believe that the lifetime of an AS path is a fundamental metric that should be considered before tagging. As far as we know, the only work that has considered the lifetime of routes is [START_REF] Oliveira | Quantifying the completeness of the observed internet as-level structure[END_REF], but the authors only set a threshold to cut off routes that lasted less than two days, potentially cutting off short-lived backup connections.

Our algorithm exploits the AS paths gathered from BGP monitors and also takes into account their lifespan during the inference of the tags, thus preserving backup links. In addition, in order to quantify the reliability of each tag we introduce the concept of two-way validation into the tagging algorithm, distinguishing between confirmed and unconfirmed tags.

The rest of the paper is structured as follows. In Sect. 2 we show the presence of false connections in BGP data and their causes. In Sect. 3 we analyze the nature of transient AS paths and we describe in detail the algorithm proposed.

In Sect. [START_REF] Gao | On inferring autonomous system relationships in the internet[END_REF] we analyze the results and we draw conclusions in Sect. 5.

BGP Data Gathering and Hygiene

BGP data is widely used in research into the Internet AS-level topology. However, to the best of our knowledge, there are not many works that analyze the correctness of the topological information retrieved. As we mentioned earlier, this kind of data could be affected by errors made during the manual configuration of BGP, which could lead to false AS paths and, thus, to non-existent connections within the AS-level topology. In this section we briefly describe the list of our data sources and how we managed to retrieve the data. We then analyze these data and we will propose a methodology in order to clean up any human mistakes.

The main public projects that are currently available are RIPE RIS and RouteViews. Route collectors (or monitors) deployed by these projects are devices that act like BGP AS border routers, but that do not send UPDATE messages, thus not announcing any prefix. Their only purpose is to establish a BGP session with BGP routers under the ownership of other ASes in order to gather routing information. To analyze the BGP table of each monitor we downloaded the snapshot of its first RIB on October 1st, 2010 and all subsequent UPDATE messages up to the end of the month. We did not only download snapshots because we might have missed all those links that are visible only between two snapshots, including some backup links. In addition, UPDATE messages allow us to trace the evolution of each single AS path and each AS connection during October 2010 in terms of its lifespan. To gather the lifespan of each AS path we rely on the BGP-4 specs (RFC 4271). A route is withdrawn from service if: a) the IP prefix that expresses the destination for a previously advertised route is advertised in the WITHDRAWN ROUTES field in the UPDATE message, b) a replacement route with the same prefix can be advertised, or c) the BGP speaker connection can be closed, which implicitly removes all routes the pair of speakers had advertised to each other from service. We consider as the lifespan of an AS path the time span in which it was considered as active by the BGP monitor, i.e. the time interval during which there is at least one active route that includes the considered AS path6 in its attributes.

Data gathered from BGP monitors need to be cleaned before being used. Several AS paths contain private AS Numbers (ASNs) and the AS TRANS number 23456 (RFC 4893). In addition, some loops can be found even if the default behavior of BGP is supposed to prevent their formation. We investigated in depth the possible causes of these loops and we found that some of them are caused by typos, as already highlighted in [START_REF] Gao | On inferring autonomous system relationships in the internet[END_REF] and these may introduce false connections. We found three major causes of loops in BGP data: a) Human error during AS path prepending. When a BGP router sends an announcement it must prepend its local ASN to the AS path field. BGP allows the manipulation of the AS path length by prepending the owned ASN multiple times to influence the routing decision of neighboring ASes. This feature is implemented through rules to identify which announcement must be affected by the manipulation of the AS path and how many times the prepending must be done. Typically these rules are set manually by administrators, thus during this setup errors may be introduced that could in turn generate loops. Table 1 uses real AS paths in order to highlight seven different kinds of human errors. b) Network Migration. Consider ISP A and B, as represented in Fig. 1a. Suppose that A purchases B, then customers of B become customers of A (Fig. 1b). The external BGP (eBGP) peering sessions with B's customers have to be reconfigured, requiring significant coordination and planning efforts. The Cisco Local-AS feature allows the migrated routers (routers formerly owned by B) to participate in AS A while impersonating AS B towards (previous) customers of AS B. Routers using the Local-AS feature retain the information that the BGP routes have passed the local AS in the AS path. They prepend B in inbound eBGP updates and prepend both current ASN A and B in outbound eBGP updates. In this environment, some loops can be introduced if (previous) customers of B exchange UPDATE messages with each other passing through AS A. A split AS is an AS that is divided into two (or more) islands. An AS can be split steadily or could split due to an internal temporary network failure. An example of a steady split AS is AS 48285 (Robtex.com). Consider the following AS path: (44581 48285 16150 5580 48285). AS 16150 and AS 5580 are respectively located in Sweden and the Netherlands. We contacted the Robtex.com administrator 7 and learnt that AS 48285 is indeed steadily split. Thus, to obtain the connectivity between the two islands, the path needs to pass through other ASes (in this case AS 16150 and AS 5580). Note that AS paths matching case a) can introduce false connections, thus it is critical to fix them so as to obtain a reliable topology. On the other hand AS paths in b) and c) will not be fixed because they reflect a real-world situation. Thus, we clean the topology by fixing typos and by not considering connections involving private ASNs and AS T RAN S. The cleaned topology contains 116672 connections and 36437 ASes.

From BGP lies to a keen tagging algorithm

The proposed tagging algorithm exploits a list of Tier-1 ASes, denoted by T list , and relies upon the following basic principle: an AS that is not included in T list should be able to reach all the Internet networks, thus there must exist at least one AS path including the considered AS and a Tier-1 AS. As in [START_REF] Oliveira | Quantifying the completeness of the observed internet as-level structure[END_REF], we use the list gathered from Wikipedia to obtain a list of Tier-1 ASes 8 . The algorithm also assumes that export policies imposed by the p2c, c2p, p2p and s2s relationships described in [START_REF] Gao | On inferring autonomous system relationships in the internet[END_REF] are respected by ASes. More specifically, it assumes that an AS announces to its customers and siblings all the routes that have been received from its customers, peers and providers, while to its providers and peers it announces only the routes received from its customers.

A fundamental characteristic of this algorithm is that it computes the economic relationships by also considering the lifespan of the AS path. The presence of transient AS paths on BGP data has already been highlighted in [START_REF] Mahajan | Understanding bgp misconfiguration[END_REF], and we found that several of them, if used, can lead to misleading results in the tagging algorithm. We strongly believe that the tagging decisions made via long lasting paths must not be affected by these transient AS paths that are not used to transit IP traffic, thus our algorithm handles them. This section analyzes this specific class of transient AS paths included in the BGP data. We then introduce a tagging algorithm that also takes into account the presence of such transient paths.

Transient AS paths

Several AS paths gathered by BGP monitors include AS connections that are not used to transit any traffic. This happens due to erroneous export policies implemented in BGP, as described in [START_REF] Mahajan | Understanding bgp misconfiguration[END_REF], where two different classes of BGP misconfigurations are listed that could induce false AS paths: origin misconfiguration and export misconfiguration. In the former, an AS accidentally announces a prefix that it should not be announced, while in export misconfiguration an AS sends an announcement to a neighboring AS which violates the commercial agreement between them. These misconfigurations are much more effective when mixed with the BGP convergence times. As stated in [START_REF] Oliveira | Quantifying path exploration in the internet[END_REF], in response to path failures some BGP routers may try a number of transient paths before selecting the new best path or declaring that a destination is unreachable, performing the so-called path exploration. We analyzed BGP data and found a specific class of 8 From http://en.wikipedia.org/wiki/Tier_1_network, the Tier-1 ASes are: AS209 (Qwest), AS701 (Verizon), AS1239 (Sprint), AS1299 (TeliaSonera), AS2914 We investigated the set of AS paths to find this particular kind of AS path and noted that, on average, 1.3% of the AS paths on each monitor belongs to this class and that the largest number of these paths lasted less than an hour. Figure 2 shows the distribution of the minimum, maximum and average lifetime of each no-valley-free AS path as seen by the route-views2 monitor of the RouteViews project. As can be seen, about 90% of these paths on route-views2 lasted 10000 seconds or less. The same behavior was found on all the other monitors.

The peak of lifetimes around 30 seconds in Fig. 2 can be explained by the fact that 30 seconds is equal to the suggested value for the MinRouteAdver-tisementIntervalTimer of BGP (RFC 4271). This timer indicates the minimum amount of time that should elapse between two consecutive announcements regarding the same route. If this default value is used by the vast majority of routers, then several short-lasting no-valley-free paths will be replaced at least every 30 seconds. One plausible explanation for several of these paths is that they are a consequence of the co-effect of the convergence of BGP protocol upon a network failure and the usage of a particular type of outbound policy operated by one of the ASes involved. In more detail, BGP allows the filter of outbound announcements to be set up on a prefix basis. The filter thus prevents an announcement carrying a network prefix that belongs to one of its providers from being propagated to its peers and providers. However this filter has a drawback that can be seen after the end of a BGP connection, either due to a temporary network failure or to the end of an agreement. Consider the scenario in Fig. 3. C uses the AS path [D] to reach prefix P, which belongs to its customer D. However, C has stored in its Adj-RIB-In 9 also the AS paths [A, B, D] and [B, Fig. 3: Scenario D], received from its providers A and B respectively. Now suppose that due to a network failure in P, D sends a withdrawal to B and C. C's BGP decision process will remove from its RIB the AS path [D] to reach network P and will search for another way to reach it before declaring to its neighbors that network P has been withdrawn. Since it has not yet received any withdrawal message from B concerning P, the direct consequence is that C will select10 [B, D]. If C performs an outbound filtering implemented as described above, it will then announce to A the route [B,D] to reach P, even if it is clearly in contrast with the p2c agreement signed with B. This is because network P appears in the list of networks that can be advertised to all the providers. Furthermore, since an AS typically prefers a route toward a customer over a route toward a peer or a provider, A will select the AS path [C, B, D] to reach P and it will announce it to the monitor M, thus causing the creation of a no-valley-free path. In practice, M sees that C is transiting traffic between its providers A and B for a short time (see Fig. 2) since the network P will be withdrawn from the Internet at the end of the convergence of BGP protocol. Note that this is an issue for the tagging algorithm, but not for the AS-level topology discovery tools. The connections among ASes that appear during these transients all exist, even though the traffic does not actually pass via the given AS path.

Tagging algorithm

The main piece of information that can be exploited to infer AS relationships is the set of AS paths that we can gather from the BGP data stored by monitors and their lifespan. After the data hygiene phase, performed as described in Sect. 2, our algorithm assigns an economic tag to each connection of the topology, which also indicates the level of reliability for each of them. The algorithm is organized in three main steps: a) inference of all the possible economic relationships for each AS connection. In this step, the algorithm analyzes every single AS path separately from the others and assigns a raw economic tag to each direct 11 In other words, B is providing A with connectivity to a portion of the Internet.

Consider now an AS path such as ( . . . T 1 . . . A B . . . ). In this case the algorithm infers that A is a provider of B (line 4), because their relationship cannot be both p2p and c2p. This is because if A and B established a p2p relationship, then A would transit traffic between one of its providers or peers (T 1 ) 12 and another peer (B), thus violating the export rules imposed by the p2p agreement. The same argument can be applied to show that A and B cannot have a c2p relationship. If the AS path considered does not contain any of the T list ASes following or preceding [A,B], the algorithm infers that A and B have a p2p relationship because neither A nor B uses the other as a provider (line 6). Note that the aim of the algorithm is not to infer the relationships among ASes included in T list , since they are assumed to be p2p. This step of the algorithm also maintains for each tagged connection the maximum lifetime of the AS paths used to infer it. b) inference of a single economic relationship for each direct AS connection. In this step, the algorithm uses the results of step a) to infer for each direct AS connection [A,B] a unique economic tag among all the tags collected in step a) Fig. 6: Step c) Final tagging and two-way validation for the same direct connection. The algorithm first orders the tags inferred for the direct connection [A,B] in descending order of lifespan. It then analyzes each tag from the longest-lasting to the shortest-lasting, as illustrated in Fig. 5 (line 2). The lifespan of each tag plays a major role, since the algorithm allows the current examined tag (Tag[A,B]) to affect the current resulting tag for the same direct connection (direct Tag[A,B]) iff its lifespan does not differ by more than N M AG order of magnitude from the longest-lasting tag found for the same direct connection, i.e. iff the two lifespans are comparable (line 4). Note that the algorithm examines each tag in descending order of lifespan, thus direct Tag[A,B] contains the longest-lasting tag for the direct connection [A,B]. With this solution, the algorithm simply ignores the transient paths to infer the economic relationship for those connections that are found both in transient and stable paths, while it still analyzes connections that are found only as short-living since it assumes that they are backup connections. The merging rules used in this step (direct merge at line 5) are reported in Table 2a and can be justified by the export policies described at the beginning of this section. If A and B have a p2c relationship, i.e. B and A have a c2p relationship, this means that A can reach only B's customers while B can reach A's customers, A's peers and A's providers. On the other hand, if A and B have a s2s relationship, A can reach B's providers B's peers and B's customers, while if A and B have a p2p relationship, they only reach their respective customers. Thus, the merge of a s2s tag with either p2c or p2p tags results in a s2s tag and the merge of a p2c (c2p) tag with a p2p tag results in p2c (c2p) tag. c) Final tagging and two-way validation. In the final step, the algorithm uses the results of step b) to infer the economic relationship for each indirect connection 13 , as illustrated in Fig. 6. For each direct [A,B] connection the algorithm first gets its resulting tag (direct Tag[A,B], line 2) and checks if there is a resulting tag for the direct connection [B,A] (direct Tag[B,A], line 3). If both exist then it checks whether their lifespans are comparable (line 4) and if necessary merges the two tags (inverse merge, line 5). The merging rules, listed in Table 2b, are very similar to those introduced in step b), but they also take into account the fact that a p2c for the [A,B] connection is a c2p for the [B,A] connection. In this step it is also possible to find which tag has a two-way validation, i.e. which tag is inferred from both the tags of the direct connections [A,B] and [B,A]. Then, a label is assigned for each tag which indicates if it is two-way validated or not, distinguishing between confirmed (line 5) and unconfirmed tags (line 7 and 9).

1 foreach direct [A,B] connection 2 get direct Tag[A,B] 3 if ( exists direct Tag[B,A])

Results

This section presents the results of the tagging algorithm obtained using N M AG = 1, 2, ∞14 . The results are shown in Table 3. Note that the number of confirmed tags is ranging from 4.5% to 6.4% for raising N M AG . However, if the value of N M AG is increased there is more probability that transient paths will affect the final tag decision, thus lowering the reliability of the algorithm itself. This is confirmed by Fig. 7 that shows the CCDF of the minimum lifespan of AS paths that participate to the tag of each connection. As can be seen from this figure, if the lifespan is not considered then a large portion of transient AS paths are contributing to the tag of each connection, possibly leading to a wrong result.

The results also highlight the presence of a large percentage of unconfirmed p2p relationships, which decrease for increasing values of N. This is caused mainly by lack of information, but also by the fact that the reverse connection that could confirm the tag is short lasting, and thus not considered by the algorithm. A particular scenario created due to lack of information is depicted in Fig. 8. The figure shows that, due to the BGP decision processes, the monitors cannot gather all the possible AS paths. Thus the results of our algorithm can be misleading.

Consider S to be the source AS, T an AS included in T list and M the monitor. Consider also that A, B, C and T are the transit providers of S, that in this case acts as a stub AS, i.e. it does not transit any IP traffic for any other AS, but only for end users. Supposing that T decides that the best path to S is via A, the AS paths that are gathered by M in the steady state of this scenario will be (T, A), (T, B), (T, C), (T, A, S), (B, S) and(C, S). Applying our algorithm to this scenario leads to a single unconfirmed p2c relationship for [A, S], while the couples [B, S] and [C, S] will be interpreted as unconfirmed p2p. This could be solved by connecting the BGP collector to the stub AS. There would thus be a higher probability to gather AS paths involving T, i.e. (S, A, T), (S, B, T) and (S, C, T), which would then transform the relationships [S, B] and [S, C] into an unconfirmed p2c.

The same scenario could be applied to small and medium ISPs, since it is the effect of BGP decision processes, and this phenomenon also introduces a large number of unconfirmed p2p which, in the real world, are p2c relationships. Some of these connections can be spotted by analyzing the stub ASes. A typical stub AS has several p2c relationships to transit ASes due to multihoming and it does not develop any p2p relationhips. Particular real world examples of this class of ASes are ASes owned by banks, car manufacturers, universities and local ISPs. To find these kinds of ASes, we analyzed all the AS paths available and we considered as stub ASes all the ASes that only compare as last hop in the AS paths, i.e. those ASes that do not transit any IP traffic for other ASes. Due to their nature these ASes are likely to be customers in the relationships that involve them, thus there is a higher probability that unconfirmed p2p relationships involving them could be turned into p2c relationships. As reported in Table 3, the large number of unconfirmed p2p relationships involving stub ASes supports this rationale. The probability of being a real p2c relationship is very high for unconfirmed p2c relationhips involving stubs. Note that if the connections involving stubs and unconfirmed p2c are considered as confirmed p2c, the percentage of confirmed tags would raise to near 60% for all the N M AG considered.

Tags inferred by the algorithm depends on the list of Tier-1 considered, thus we investigated its correctness. Wikipedia is a web-based encyclopedia that any- one can edit, so the list can be the result of multiple manipulations. On the other hand, the web page containing the list of Tier-1 ASes concerns a very specific and technical topic and it is hard to believe that a common user without any particular skill in this subject could build up a detailed list like that. The presence of a low number of AS paths that include three consecutive ASes of the T list would seem to indicate that it is incorrect, because these patterns would only be able to seen if the Tier-1 ASes were not all interconnected via settlement-free peering relationships, since in this case one of them is transiting traffic for others. For example, route-views2 spot 239 different AS paths showing this pattern. Since, on average, on each route collector 20% of the AS paths that match this pattern last more than one hour, they are very unlikely to represent only simple transient paths created through router misconfigurations. In our future work we plan to study in detail the ASes that make up the core of the Internet.

Conclusion

We have exploited BGP data to discover what economic relationships are established between couples of ASes using an algorithm that works directly on BGP raw data. We found that BGP data can contain several anomalous paths that are clearly in contrast with the valley-free rule introduced in [START_REF] Gao | On inferring autonomous system relationships in the internet[END_REF]. We traced their dynamics over a month and discovered that most of them lasted very few seconds and that they are the result of the combination of a particular common BGP Fig. 8: BGP monitor placement pitfalls misconfiguration and the BGP convergence delay. Our algorithm is keen of these events and is able to handle them using the lifespan of each AS Path. To infer the relationship, the algorithm relies on a priori knowledge of a list of Tier-1 ASes in order to understand whether an AS is transiting traffic for another AS.

Using the concept of two-way validation, this algorithm is also able to assign a level of reliability to each inferred tagged connection from the Internet topology. It does this in order to compensate for the drawbacks introduced by the incompleteness of the BGP data in our possession. Our results indicate that current BGP datasets can select the two-way validated economic relationship only in 4.5 -6.4% of the connections depending on the N M AG considered. Further work will study methodologies to obtain a much higher coverage.

Fig. 1 :

 1 Fig. 1: Network Migration Scenario

Fig. 2 :

 2 Fig. 2: CCDF of the lifespan of no-valley-free AS paths

Fig. 4 : 2 foreach 7 direct

 427 Fig. 4: Step a) of the algorithm

Fig. 5 :

 5 Fig. 5: Step b) of the algorithm

4 if 6 else 7 unconfirmed 8 else 9 unconfirmed

 46789 ( lifespan [direct Tag[B,A]] and lifespan [direct Tag[A,B]] are comparable) 5 confirmed Tag[A,B] = inverse merge(direct Tag[A,B], direct Tag[B,A]) Tag[A,B] = direct Tag[A,B] Tag[A,B] = direct Tag[A,B]

Table 2 :

 2 Rules to merge tags (resulting tags are referred to the connection (A,B)) (a) Direct Merge [A, B] [A, B] p2c p2p c2p s2s p2c p2c p2c s2s s2s c2p s2s c2p c2p s2s p2p p2c p2p c2p s2s s2s s2s s2s s2s s2s (b) Inverse Merge [B, A] [A, B] p2c p2p c2p s2s p2c s2s p2c p2c s2s c2p c2p c2p s2s s2s p2p c2p p2p p2c s2s s2s s2s s2s s2s s2s

Fig. 7 :

 7 Fig. 7: CCDF of min lifespan of AS paths used

Table 1 :

 1 Loops caused by human errors

	Error type	(Real) Example
	Lack/excess of a trailer digit 3561 26821 27474 2747 27474
	Lack/excess of a header digit 286 3549 9731 38077 8077 38077
	Lack/excess of a middle digit 13030 1273 9329 929 9329
	Missing space between ASNs . . . 2152 3356 35819 3581935819 35819 35819. . .
	Error on a digit	13030 22212 19024 25782 25785 25782
	Error on two digits	11686 4436 3491 23930 23390 23930 7306
	Missing digit cause split ASN 6939 5603 21441 21 41 21441

Table 3 :

 3 Tag results

	Unconfirmed

The node degree of a vertex of a graph is the number of edges incident to the vertex. In our case, degree indicates the number of BGP neighbors of an AS.

The RFC 4271 defines a route as "the unit of information that pairs a destination with the attribute of a path to that destination". In this case, the attribute that we are considering is the AS path.

We would like to thank Robert Olsson, administrator of robtex.com, for the collaboration.

Each BGP router maintains a Adj-RIB-In (Adjacent Routing Information Base, Incoming) containing troutes received from neighbors.

For simplicity's sake, we consider the length of AS paths as the only relevant decision factor in BGP decision process

We denote as direct connection a connection in which the direction is relevant i.e. the direct connection [A,B] is different from the direct connection [B,A].

By definition a Tier-1 AS does not have any provider.

We denote as indirect connection a connection in which the direction is not relevant, i.e. the indirect connection [A,B] is equal to the indirect connection [B,A].

NMAG = ∞ represents the case in which the lifespan is not considered i.e. every AS path contribute to the tagging algorithm outcome.

This paper was was partly supported by the MOTIA European Project (JLS/2009/CIPS/AG/C1-016). This publication reflects the views only of the authors, and the Commission cannot be held responsible for any use which may be made of the information contained therein.