Muhammad Qasim Pasta
email: mqpasta@pafkiet.edu.pk

Zohaib Jan
email: zohaib.jan@szabist.edu.pk

Shaheed Zulfikar

Ali Bhutto

Arnaud Sallaberry
email: arnaud.sallaberry@lirmm.fr

Faraz Zaidi

Tunable and Growing Network Generation Model with Community Structures

based on the simulation and modeling of networks with domain dependent as well as domain independent characteristics. Furthermore, these models help us understand the underlying processes and structural changes taking place in many diverse real world networks.

An important characteristic of these networks is the presence of community structures. Networks in general and social networks in particular highly depend on a society based structure where groups of people are very well connected to each other and sparsely connected to people from other groups [7]. This phenomena has been observed in networks from many different domains such as computer networks [8], biological networks [9] and maritime transportation networks [10]. A number of network studies depend on the underlying community structure present in a network [11]. For example, [12] studied communities of scientists and the role of information diffusion in the creation of knowledge. [13] studies the effects of communities on the immunity coverage required to prevent disease epidemics in societies. Tunable methods that can generate networks with desired network characteristics and the presence of communities can be very useful in such studies as they can provide a benchmark for empirical evaluation. Researchers [14], [15] have proposed different models to generate networks with community structures in an attempt to generate networks which are topologically similar to real world networks.

An important feature often overlooked by different network generation models with community structures is the topological structure of a community itself. Usually models propose increased intra-community links and reduced intercommunity links but the connectivity within a community is ill defined or follow only power-law degree distribution. The major contribution of the model is that we maintain three important topological characteristics within each community:

• • •
The degree distribution of nodes follows a power-law.

The clustering coefficient is high.

Each community can be further divided into subcommunities, i.e. there are hierarchical communities Abstract-Recent years have seen a growing interest in the modeling and simulation of social networks to understand several social phenomena. Two important classes of networks, small world and scale free networks have gained a lot of research interest. Another important characteristic of social networks is the presence of community structures. Many social processes such as information diffusion and disease epidemics depend on the presence of community structures making it an important property for network generation models to be incorporated.

In this paper, we present a tunable and growing network generation model with small world and scale free properties as well as the presence of community structures. The major contribution of this model is that the communities thus created satisfy three important structural properties: connectivity within each community follows power-law, communities have high clustering coefficient and hierarchical community structures are present in the networks generated using the proposed model. Furthermore, the model is highly robust and capable of producing networks with a number of different topological characteristics varying clustering coefficient and inter-cluster edges. Our simulation results show that the model produces small world and scale free networks along with the presence of communities depicting real world societies and social networks.

I. I NTRODUCTION

Traditionally graph and network studies were made using regular and random graphs [1] until the late 1990's when two ground breaking discoveries were made about real world networks. The presence of low average path lengths and high clustering coefficients lead to the discovery of small world networks [START_REF] Watts | Collective dynamics of 'small-world' networks[END_REF] and the study of degree distribution following power-law lead to the discovery of scale free networks [START_REF] Barab´ | Emergence of scaling in randoma networks[END_REF]. These topological characteristics are commonly present in many real world networks such as social networks [START_REF] Watts | Six Degrees: The Science of a Connected Age[END_REF], biological networks [START_REF] Dorogovtsev | Evolution of networks[END_REF] and information networks [6].

The discovery of small world and scale free properties have catalysed the research in the area of developing new graph and network generation models as networks with these properties appear readily across different and contrasting domains. This research area presents interesting challenges and new horizons for researchers to develop theories, models and algorithms in the network Each of the above characteristics has associated social semantics. Consider a co-authorship network where researchers collaborate to author manuscripts. Each research group represents a community as members regularly collaborate to increase intra-cluster edges which in turn results in high clustering coefficient. Subsequently, this research group also belongs to the community of researchers working in the same area across different research labs and different countries. These researchers collaborate less frequently but have still more edges when compared with research groups working in different domains. This creates a hierarchical community structure in the co-author network as argued by other researchers as well [16]. Each research group is usually headed by a senior professor with research publications, which means that a senior professor will have a high number of co-authors. Structurally this implies that the senior professor will have many edges connecting it to many authors. Usually each research group has a few senior researchers with high publication profile and the rest of the team comprises of researchers with low publications. These researchers are often associated with the senior professors while authoring an article justifying that every community demonstrates scale invariance power-law. Similarly the group dynamics and synergy is reflected by the people within a research group collaborating to author manuscripts. This results in a high number of triad formation which in turn results in high clustering coefficient for members of a research groups depicting a community.

The contribution of this paper is that we propose a new network generation model. The proposed model is inspired by [17] to generate networks with small world and scale free properties where we modify it to introduce community structures. The model caters the three described features present in community structures which is fundamental to many real world networks and specially in the case of social networks. Parameters to control inter-cluster connectivity and triad formation gives us more flexibility over the generation process and thus enables us to generate networks with desired properties. The networks produced using the proposed algorithm also exhibit small world and scale free properties. The model is tunable and robust as it can be used to generate a variety of networks by varying different parameters such as only scale free networks with community structures and networks with varying intercluster edges.

The rest of the paper is structured as follows: In the next section, we review the literature related to network generation models. Section III describes the proposed model whereas section IV analyses and explains the use of different parameters to generate networks with varying structural properties. Section V presents the results of the evaluation of the networks generated using the proposed model satisfying the small world and scale free properties with clear community structures. Finally we conclude in section VI giving future research directions.

A. Models for Random, Small World and Scale Free Networks Earlier studies related to network models were focussed on generating random graph. Most notable work of all is the graph generation model by [1]. Molloy and Reed [18] proposed a model to generate graphs with desired degree distribution. Watts and Strogatz proposed the famous model to generate small world networks [START_REF] Watts | Collective dynamics of 'small-world' networks[END_REF] where the algorithm starts with a regular graph and random rewiring of edges based on some probability results in a small world graph with small average path length and high clustering coefficient. Albert and Barabasi introduced another important model [START_REF] Barab´ | Emergence of scaling in randoma networks[END_REF] based on preferential attachment to generate scale free networks.

Since the discovery of small world and scale free networks, a number of network models have been proposed to generate networks with these two properties. Most of these models are variants of the two basic models [START_REF] Watts | Collective dynamics of 'small-world' networks[END_REF], [START_REF] Barab´ | Emergence of scaling in randoma networks[END_REF] discussed above. For example Holme and Kim [17] introduce a triad formation step after the preferential attachment step in [START_REF] Barab´ | Emergence of scaling in randoma networks[END_REF] which creates triads in the network increasing the overall clustering coefficient. Other variants such as [START_REF] Dorogovtsev | Evolution of networks[END_REF], [19]-[24] produce networks by introducing triads one way or the other and nodes connect using the preferential attachment rule to have a scale free degree distribution.

Another approach for generating small world and scale free networks is the use of n-partite structure. Newman et al. [25] study a network generation model with arbitrary degree distribution. The goal is to generate affiliation networks similar (such as co-authorship network [6]) using random bipartite graphs. Guillaume and Latapy [26] also used a similar idea as they identify bipartite graphs as an underlying structure for networks with small world and scale free properties. Bu et al. [27] used a n-partite structure, which is simply a generalization of the earlier proposed models. Good references on network generation models can be found in [28]-[30].

B. Models for Networks with Community Structures

Li and Chen [31] introduced a model for weighted evolving networks with community structures. The model incorporated three types of power-law distributions, first on the node degree, second on link weights and third on node strengths along with the presence of clear communities. The model does not produce networks with high clustering coefficient as nodes within a community do not follow triadic closure property. Xie et al. [32] proposed a community-based evolving network model where they focus on the cumulative distribution of community sizes which also follows power-law in real world networks. As a result, when new connections between communities are added, or a new node to an existing community is added, communities with larger sizes are selected preferentially. Zhou et al. [33] identify two important topological characteristics, first, intra-cluster connections are very dense as compared to inter-cluster connections and second, size of communities often follows a power-law just as [32] proposed. Based on these characteristics, they propose a weighted growing model with power-law distributions of community sizes, node strengths, and link weights.

II. R ELATED W ORK

We divide the literature review into two logical subsections. Kumpula et al. [34] utilize the concepts of cyclic closure and focal closure from sociology to propose a model to generate a weighted network with communities. New links are created preferably through strong ties which make these links more stronger. The model also allows the removal of nodes to mimic real world scenarios where nodes may leave a network. Xu et al. [35] introduce a model with communities that gives a realistic description of local events using three processes, adding new intra-community nodes, new intracommunity links or new inter-community links. The model uses preferential attachment mechanism resulting in power law degree distribution but since the intra-community links only connect on the basis of node degree, the network lacks triads, producing networks with low clustering coefficients. Lancichinetti and Fortunato [15] propose an algorithm to generate benchmarks to test clustering algorithms for directed/undirected and weighted/unweighted graphs with optional overlapping communities. This algoritm produces networks following power-law distribution for node degree as well as community sizes. They do not address the internal structure of each community as we do in this paper. Badham and Stocker [29] propose a spatially constructed algorithm to generate networks with tunable degree distribution, clustering coefficient and assortativity with the objective that such models should be flexible to generate networks with varying values of these properties giving more control over the generation process. They do not explicitly include the generation of community structures in their model. Ren et al. [36] study the connecting patterns among existing papers in co-authorship networks and highlight that existing models cannot correctly model high clustering in such networks. Their proposed model can generate networks with power-law degree distribution, high clustering coefficient and the size distribution of co-citation clusters as observed in coauthorship networks. Moriano and Finke [37] also propose a model with small world and scale free properties along with groups of nodes densely connected to each other and sparsely connected with other nodes. The model helps to explain networks with extended power law degree distributions and clustering coefficient that does not diminish as the size of the network grows very large. The connectivity of new nodes probabilistically chooses nodes of same type or different type to form community structures. Zaidi [30] proposed a model to generate clustered small world networks. The author first demonstrates that small world networks can be produced from completely random graphs by introducing a little order in them, which is a contrasting approach to the famous model of [START_REF] Watts | Collective dynamics of 'small-world' networks[END_REF]. The further extends this model to generate clustered networks with small world properties where communities connect randomly to other communities. The model does not generate scale free networks. Zaidi et al. [38] also proposed a static network generation model with community structures i.e nodes added at the start remain the same throughout the algorithm and only edges are rewired to create communities. The model is probabilistic and increases the edge connectivity among nodes closer to each other and reduces edges among nodes far apart in the network. Step 1 with c=3 triads where every triad is connected to every other triad. [START_REF] Watts | Collective dynamics of 'small-world' networks[END_REF] Step 2, A new node n1 is added and forms a triad with probability Pt with a neighbor of n2 . [START_REF] Barab´ | Emergence of scaling in randoma networks[END_REF] Step 4, A new node n3 is added and forms a triad with probability Pt with a neighbor of n4 . [START_REF] Watts | Six Degrees: The Science of a Connected Age[END_REF] Step 6, The communities of newly added nodes n1 and n3 which are selected on the basis of preferential attachment forms an inter-cluster edge with probability Pc .

But the process is not a growing one, and it is not parametrized to generate desirable clustered network as compared to the model proposed in this study. Furthermore this model does not ensure the presence of the three structural properties for a community discussed in the introductory section of this paper.

All the different models for generating networks with community structures discussed above do not focus on the internal structure of communities just as we do in this paper. We focus on three structural properties present in our society and propose a model to simulate these properties.

III. P ROPOSED M ODEL

The model takes as input the desired number of nodes in the network n, the number of edges for each newly added node m, the minimum number of communities c, the probability of triad formation Pt and probability Pc of having inter-cluster edges. The model starts with an empty network. Rest of the steps are explained below:

1)

Add c triads representing c communities in the network. Each node in a triad belongs to the community of the triad. Every community thus created is then connected to every other community. An edge is created between randomly selected nodes from different 2)

3)

communities. This step generates a graph as shown in figure 1(1).

Add a new node n1 and connect it to an existing node n2 which is selected on the basis of preferential attachment. Now n1 belongs to the community of n2 as shown in figure 1(2). With probability Pt , either n1 connects to m -1 preferentially selected neighbors of n2 belonging to the same community as n2 forming a triad or n1 connects to other nodes preferentially selected from the community of n2 (which might not necessarily be a neighbor of n2 ). Figure 1(2) shows that the newly added node connected to one of the neighbors of n2 .

Add a new node n3 and connect it to an existing node n4 which is again selected on the basis of preferential attachment. Now n3 belongs to the community of n4 . We make sure that n3 does not belong to the community of the node added in the previous nodeaddition step to the network. Figure 1(3) shows this step.

With probability Pt , either n3 connects to m -1 preferentially selected neighbors of n4 belonging to the same community as n4 forming a triad or n3 connects to other nodes preferentially selected from the community of n4 ( which might not necessarily be a neighbor of n4 ), as shown in Figure 1(3). With probability Pc , add an edge between two preferentially selected nodes belonging to the two communities to which nodes were added in the previous steps, which is the communities of n2 and n4 as shown in figure 1 As described above, the model uses five parameters, n, m, c, Pt , Pc . The parameter n defines the number of nodes desired in the final network and m defines the number of connections each newly added node will have in the network (except for the nodes added in the initial triads in step 1).

Preferential Attachment for individual nodes: The probability of a new node preferentially selecting an existing node ni from the set of current vertices V is a function of the degree of node ni which can be calculated using:

P (nk ) = degree(nk ) , ∀j ∈ V degree(nj )
This ensures that communities of different sizes evolve in the network where the degree distribution of community sizes follow scale free behavior. This is because new nodes select a node to attach based on its degree, which in turn implies that a community is selected based on preferential attachment of nodes present in a community as shown in the above equation.

Minimum Number of Communities c: This parameter controls the minimum number of communities we want to generate in the network. Further Communities and subcommunities form as order emerges from the connectivity of new nodes entering the network probabilistically. As the number of nodes increases, sub-communities increase depicting the natural evolution process of communities in real world networks. A simple variation for this parameter would be to use the value 1 signifying only 1 community, along with the triad formation step using Pt , the behavoir of the network would be the same as the model proposed by [17]. Small sub-communities will still form in this network but they will not be clearly separable. Another important variation would be if we use c = 1, m = 1 and Pt = 0 i.e. eliminating the triad formation step, the model generates random scale free networks similar to [START_REF] Barab´ | Emergence of scaling in randoma networks[END_REF].

Probability of Triad Formation Pt : This parameter controls the presence of triads in the network. The triad formation step is performed with a probability Pt , or a preferential attachment step is performed with probability 1 -Pt instead of triad formation step. Both the triad formation step or preferential attachment step, the new node is only connected to nodes from the same community. A value of Pt = 0 means This ensures that the nodes are selected based on preferential attachment.

Preferential Attachment for each community: The probability that a new node selects a community ck to attach can be estimated as:

P (ck ) = degree(ni ) , ∀i ∈ ck , ∀j ∈ V degree(nj )
As the network grows, the community sizes vary as a function of the high degree nodes present in that community. Pc = {0.01, 0.1, 0.5, 1.0} which makes 32 different combinations. We used m = {2} for all performed experiments which means that every new node entering the network has degree 2 to start with, which increases probablistically as other new nodes select previously added nodes as their connections.

Table I shows all these combinations and a key is assigned to each combination to uniquely identify a network and the parameters used to generate it. For each of these parameter values, we generated 5 networks each, and used the average of the metrics obtained as a result, eliminating potential outliers and exceptions that might bias the ultimate results as the algorithm is probabilistic in nature.

Figure 2 show the values of average path length, average clustering coefficient and power-law coefficient(alpha) for all the generated graphs. This is to demonstrate that our graphs are indeed small world and scale free networks. All the graphs have an average path length between 3 and 7. Path lengths of around 7 are observed in networks where we introduce inter-cluster edges with a probability of 0.01. This results in clearly separated communities with very little inter-cluster edges, which in turn results in increased distances among nodes from different clusters. For the clustering coefficient values, we used two parameter values, 0.5 where triads are formed only for 50% newly added nodes with m edges giving CC values in the range of 0.3 and 0.5, and the parameter value 1.0 where all nodes and edges added to the network belong to at least one triad which raises the CC around 0.65. Finally for the alpha value, since all our connectivity is based on preferential attachment, all the 32 generated networks have values between 2 and 3.

In order to show the presence of community structures in the generated networks, we used two well known metrics, Modularity (Q) [39] and Relative Density [40]. We clustered the generated graphs using the method proposed by Newman [41] which generates flat clusters. We calculated the Q and RD values which are shown in figure 3. Consistently high values clearly demonstrate the presence of community structures present in the networks. As the inter-cluster edges are increased, both Q and RD values decrease implying that the control parameter Pc can be used to generate communities with low or high inter-cluster edges which subsequently affects the Q and RD values. that in steps 3 and 5, triads are not formed, as a result of which the overall clustering coefficient remains quite low. The network thus generated is a random scale free network with communities. A value of Pt = 1 would mean that every node added to this network with m edges, forms triads for every edge making the overall clustering coefficient quite high as is the case for small world networks.

Probability of Inter-cluster Edges Pc : The inter-cluster density is controlled through this probability. A value of Pc = 0 means that no further intra-cluster edges would be added to the network as described in step 6. This results in well separated communities with exactly two intra-cluster edges for each community which were added in step 1. These edges are added so that the final network obtained, remains a connected network. A value of Pc = 1 results in high inter-cluster edges making it difficult to distinguish communities structurally.

We demonstrate the effects of varying these parameters empirically in the next section as we generate numerous networks using the proposed model.

V. E XPERIMENTATION AND R ESULTS

We tested the proposed model with the parameter values of n = {1000, 10000}, c = {10, 20}, Pt = {0.5, 1.0} and I) generated from the proposed model. Both these networks show community structures with different color encodings for the top 10 communities in terms of size. More communities with smaller sizes are encoded with yellow color. To prove our claim that the communities thus produced follow power-law degree distribution with high clustering coefficient, we plotted the power-law coefficient and clustering coefficient of the top ten communities in terms of node-size for the two graphs presented in figure 4. Figure 5 shows the power-law coefficient which lies in the range [START_REF] Watts | Collective dynamics of 'small-world' networks[END_REF][START_REF] Barab´ | Emergence of scaling in randoma networks[END_REF] clearly showing that the communities thus produced follow scale free behavior. Similarly figure 6 shows high clustering coefficient values for the biggest communities in networks 5 and 6 reaffirming that formation of triads ensures that communities have a large number of triads.

in Table

Finally to show the scalability of the proposed model, we plot the execution times for the generation of different size networks in Table II times given in the table are on a standard intel core i5 machine with 4Gb Ram.

In terms of complexity of the proposed algorithm, the most complex task is the calculation of probability for a new node entering the network based on preferential attachment. This task, in the worst case requires n * nclarge steps where n is the desired number of nodes in the network and nclarge is the number of nodes in the largest community. The preferential attachment probability for every node added to the network is calculated in the worst case, with every other node in the largest community. If a network is generated with only a single community, nclarge becomes n and the complexity of the entire algorithm would then become O(n2 ). For a network where the community sizes are sparsely distributed, as is the case with many real world networks, this complexity becomes O(n * nclarge ) with nclarge << n.

VI. C ONCLUSION [10]

[11]

[12]

[13]

[14]

[15]

[16]

In this paper, we have introduced a new tunable and growing network generation model which incorporates the well known world and scale free properties as well as the presence of community structures. The model incorporates three important features of community structures from our society. First, the node degree distribution within a community follows power-law behavior, second, the clustering coefficient within communities is high and finally there is a hierarchical community structure within communities. The model is very flexible and robust and can be used to generate a variety of networks as per requirements. These characteristics can be very useful for generating benchmark and test datasets for empirical studies. Although the model is flexible, but it does not include domain dependent knowledge and cannot be used to generated networks with structural properties other than community structures, small world, scale free and random. This work can clearly be extended to generate networks for particular domains such as biological networks, computer networks. Further more, the current model does not simulate the dynamic changes like removal of previously added nodes or edges, changing previously added edges which are important characteristics for the recently studied social networks. We intend to extend this study towards this direction as well.

Fig. 1 .

 1 Fig. 1. Steps of the proposed model. (1)Step 1 with c=3 triads where every triad is connected to every other triad.[START_REF] Watts | Collective dynamics of 'small-world' networks[END_REF] Step 2, A new node n1 is added and forms a triad with probability Pt with a neighbor of n2 .[START_REF] Barab´ | Emergence of scaling in randoma networks[END_REF] Step 4, A new node n3 is added and forms a triad with probability Pt with a neighbor of n4 .[START_REF] Watts | Six Degrees: The Science of a Connected Age[END_REF] Step 6, The communities of newly added nodes n1 and n3 which are selected on the basis of preferential attachment forms an inter-cluster edge with probability Pc .

Fig. 3 .

 3 Fig. 3. Values of Modularity (Q)-Blue Bar and Relative Density (RD)-Maroon Bar, obtained after running a clustering algorithm on the generated networks. High values suggest the presence of community structures in the generated network.

Figure 4 (

 4 Figure 4(a,c) are two sample networks (Network 5 and

Fig. 2 .

 2 Fig. 2. Different metrics calculated for the 32 generated graphs showing that the graphs are indeed small world and scale free. (a)APL=Average Path Length (b) CC=Clustering Coefficient (c)) Alpha=Power-law coefficient.

Fig. 5 .

 5 Fig. 5. The graph shows the values of power-law coefficient for the top 10 communities in terms of size for the two networks shown in 4. All the values are consistently between 2 and 3 aprrox. Network 5 has parameters: n = 1000,c = 10,Pt = 1.0,Pc = 0.01 and Network 6 with parameters:n = 1000,c = 10,Pt = 1.0,Pc = 0.1.

Fig. 6 .

 6 Fig. 6. The graph shows the values of clustering coefficient for the top 10 communities in terms of size for the two networks shown in 4. All the values are consistently above 5. Network 5 has parameters: n = 1000,c = 10,Pt = 1.0,Pc = 0.01 and Network 6 with parameters:n = 1000,c = 10,Pt = 1.0,Pc = 0.1.

Figure 4 (

 4 Figure 4(b) shows Network 5 where larger clusters contain clear separation and can be re-clustered to form hierarchical community structures. Some of these clusters are highlighted and can be visually compared with Figure 4(a).

  Fig. 4. Figure shows the graphical representation of the networks generated using the proposed model. (a) Network 5 with clearly seperated communities. The top 10 communities in terms of size are uniquely colored and smaller communities are colored in yellow. (b)Network 5 with smaller communities outlined within larger communities. (c) Network 6 with more inter-cluster edges and less seperation between communities.

TABLE I .

 I T HE TABLE SHOWS THE 24 DIFFERENT COMBINATIONS POSSIBLE FOR 4 PARAMETERS AND DIFFERENT POSSIBLE VALUES . T HE SERIAL NUMBER WILL BE USED AS A KEY TO IDENTIFY NETWORKS AND THEIR PARAMETERS USED .

TABLE II .

 II T HE TABLE SHOWS THE RUNNING TIMES IN SECONDS FOR GENERATING DIFFERENT SIZE NETWORKS USING THE PROPOSED MODEL .

	[8]
	[9]


Aneeq Hashmi
email: aneeq.hashmi@nu.edu.pk

Faraz Zaidi

Arnaud Sallaberry
email: asallaberry@ucdavis.edu

Tariq Mehmood
email: tariq.mehmood@nu.edu.pk

Are all Social Networks Structurally Similar? A Comparative Study using Network Statistics and Metrics

The modern age has seen an exponential growth of social network data available on the web. Analysis of these networks reveal important structural information about these networks in particular and about our societies in general. More often than not, analysis of these networks is concerned in identifying similarities among social networks and how they are different from other networks such as protein interaction networks, computer networks and food web.

In this paper, our objective is to perform a critical analysis of different social networks using structural metrics in an effort to highlight their similarities and differences. We use five different social network datasets which are contextually and semantically different from each other. We then analyze these networks using a number of different network statistics and metrics. Our results show that although these social networks have been constructed from different contexts, they are structurally similar. We also review the snowball sampling method and show its vulnerability against different network metrics.

I. I NTRODUCTION

, and social relations include searching individuals of similar interest, establishing discussion forums and exchanging personal information [2] with friends and family members distantly located.

 only present

in social networks where individuals of similar degree have the tendency to connect to each other. Another dimension is to study how these online social networks are similar to real world social networks [START_REF] Howard | Analyzing online social networks[END_REF]. Not much attention has been given to the differences and similarities of contextually and semantically different online social networks.

Semantics and context refer to how social relations are created among individuals such as, direct communication through an email, personal liking of photograph, or being part of a common group or community. These different forms of social networks [START_REF] Rosen | Social networks and online environments: when science and practice co-evolve[END_REF] raises the question of whether different social networks have the same network structure or are they structurally different as they change from one form to the other.

In this paper, we address this question and try to answer it empirically. We use five different social network datasets and compare them using different network statistics and metrics. Our results show high similarity among structural behavior of these networks with only slight differences. Major contributions include highlighting structural similarities and dissimilarities among different social networks. We also review different network sampling methods and focus on the most widely accepted snowball sampling method. Our experiments show that this method does not always produce correct samples in terms of structural properties of a network and one should be careful when drawing conclusions when this method is used.

The rest of the paper is organized as follows: In the next section, we review the literature where online social networks have been analyzed. Section III describes the data sets used for experiemtation. In sections IV and V, we review a number of network statistics used for comparative study of networks. Section VI describes how the samples were collected and the shortcomings of the snowball sampling method. We comparatively analyze different networks in section VII and finally we draw conclusion and discuss future research prospects in section VII.

II. R ELATED W ORK

A. Analysis of Online Social Networks Jacob Moreno's [START_REF] Moreno | Who shall survive? Nervous and Mental Disease[END_REF] seminal work on runaways from the Hudson school for girls gave birth to sociometry. Since then, this field has grown steadily. Recent interest in this field was triggered by the work on small world [START_REF] Watts | Collective dynamics of 'small-world' networks[END_REF] and scale free networks [START_REF] Barab´ | Emergence of scaling in random networks[END_REF]. Further thrust to this field was given by the availability of large size social network data from online sites such as Facebook and Twitter. Since then, many researchers have actively pursued research in social network analysis (SNA) mainly due to its wide application in different fields of research ranging from genetics to nanoelectronics, from disease epidemics to product marketing. We briefly review some literature related directly to using online social network data.

Garton et al. [START_REF] Garton | Studying online social networks[END_REF] emphasized that earlier, research effort concentrated on studying how people use computers to communicate (computer mediated communication) rather than studying the social networks generated by this medium. They describe methods to identify sources to collect and analyze social network data focusing on how online communication systems provide a perfect platform to study virtual communities and interaction networks.

Kumar et al. [START_REF] Kumar | Structure and evolution of online social networks[END_REF] study the structural evolution of large online social networks using Flickr and Yahoo! 360 data sets. The authors found that the network density followed similar patterns concluding that both the graphs are qualitatively similar. They classified these networks in singletons who don't take part, a large core of connected users and a region of isolated communities forming a star structure.

Ahn et al [START_REF] Ahn | Analysis of topological characteristics of huge online social networking services[END_REF] compare the structure of three online social networks: Cyworld, MySpace, and Orkut. They observe a multi-scaling behavior in Cyworld's degree distribution and that the scaling exponents of MySpace and Orkut are similar to those from different regions in the Cyworld data. They also validate the snowball sampling on Cyworld using degree distribution, clustering coefficient, degree correlation (also known as assortativity) [START_REF] Newman | Mixing patterns in networks[END_REF] and average path length.

Mislove et al. [START_REF] Mislove | Measurement and analysis of online social networks[END_REF] use Flickr, LiveJournal, Orkut, YouTube using degree distribution, in-degree and out-degree, average path length, radius, diameter and assortativity metrics. Their analysis shows that social networks differ from other networks as they exhibit much higher clustering coefficient. They also show that social network have a higher fraction of symmetric links.

Leskovec et al. [START_REF] Leskovec | Microscopic evolution of social networks[END_REF] studied Flickr, Delicious, Answers and LinkIn to develop a network evolution model. They also discuss how the number of connections drop off exponentially with individuals more than 2 hops away. Another interesting result from this study pointed the differences in the growth of new members where Flickr grows exponentially, LinkIn grows quadratically, Delicious grows superlinearly and Answer grows sublinearly.

Lewis et al. [START_REF] Lewis | Tastes, ties, and time: A new social network dataset using facebook.com[END_REF] investigate Facebook data emphasizing five distinct features. First, the correctness of data is ensured as it is downloaded from the internet avoiding classical problems of interviewer effect [START_REF] Campbell | Social resources and socioeconomic status[END_REF], imperfections in recall [START_REF] Brewer | Forgetting of friends and its effects on measuring friendship networks[END_REF] and other measurement errors. Second, the dataset is complete as it contains information about all the existing social ties in the network. Third, the data is collected over four years allowing temporal analysis of the social dynamics taking place in the network. Fourth, data on social ties is collected for multiple social relations: Facebook Friends, Picture Friends and Housing Friends. Finally, with users providing data for their favourite music, movies and books: the dataset is quite rich and provides new research opportunities.

Benevenuto et al. [START_REF] Benevenuto | Characterizing user behavior in online social networks[END_REF] use an entirely different approach to study and analyze social networks by studying the click streams generated when a user accesses a social network site. Four online social networks: Orkut, MySpace, Hi5 and LinkedIn were used to collect data of 37024 users over a 12day period. The authors studies patters such as how frequently and for how long people connect to these networks, and how frequently they visit other people's pages. They also compared the click stream data and the topology of the friends social network of Orkut. Results reveal publicly visible social interactions such as commenting profiles as well as silent social interaction such as viewing profile and photos.

Rejaie et al [START_REF] Rejaie | Sizing up online social networks[END_REF] study MySpace and Twitter with the intent of finding the active population of these networks. They develop a measurement technique using the numerical user IDs assigned to each new user and the last login time of each user. This in turn helps to identify short lived users on the site and are termed as tourists. Results show that the number of active users in these networks is an order of magnitude smaller than the total population of the network.

Interesting observations about online social networks can be found in [START_REF] Howard | Analyzing online social networks[END_REF]. More comprehensive and recent review of literature on social networks can be found in [START_REF] Borgatti | Network analysis in the social sciences[END_REF], [START_REF] Scott | The SAGE Handbook of Social Network Analysis[END_REF]. A number of softwares have been developed for the analysis of social neworks such as UCINET, PAJEK and TULIP to support analysis and mining tasks on networks.

B. Network Statistics and Metrics

There are a number of network statistics and metrics in the literature. A detailed description of the metrics we have used is given in section IV and section V. We consider node metrics that are widely used in the research community, or the most representatives ones as these basic metrics have been used to derive new variants. For example, we have used betweenness centrality [START_REF] Freeman | A set of measures of centrality based on betweenness[END_REF] instead of stress centrality [START_REF] Shimbel | Structural parameters of communication networks[END_REF] which simply counts the absolute number of shortest paths.

Another criterion of selecting the metrics we have used is that they are all applicable on undirected networks. For example, Burt's constraint [START_REF] Burt | Brokerage and Closure[END_REF] to calculate the local cohesiveness is calculated for directed graphs only. although some of the networks that we are using are directed in nature, but we limit our study to only undirected graphs.

An important class of networks that we have not considered in this study is the metrics calculated on edges. A good resource to review these metrics is the book by Brandes and Erlenach [START_REF] Brandes | Network Analysis : Methodological Foundations[END_REF].

III. DATA S ETS

We have used a number of different data sets representing a variety of social networks used for analysis by the research community. The data sets are described below:

Twitter Friendship Network: Twitter is one of the most popular social networks in the world. A friendship network is extracted by crawling the twitter database using the api1 . Given a single user, the api returns a list of all the friends of the given user. We recursively applied this method to gather data of 2500 users starting from a single user. The complete network has 22002 edges.

Epinions Social Network: This is a who-trust-whom online social network of a customer analysis site Epinions.com2 . Members of the site can either agree or disagree to trust each other. All the reliable contacts interact and form a of Trust which is then shared with users on the basis of review ratings. We have downloaded this data from the stanford website3 where it is publicly available in the form of a text file. The network contains 75879 nodes and 508837 edges.

Wikipedia Vote Network: Wikipedia is a free encyclopaedia which is written collectively by assistants around the world. A small number of people are designated as administrators. Using complete dump of Wikipedia page edit history, we selected all administrator elections and vote history data. Users are represented by nodes in the network and a directed edge from node i to node j represents that user i voted on user j. Again, the data is available from stanford website with 7115 nodes and 103689 edges.

EU Email Communication Network: This network was generated by using email data from a huge European research institution. Information was collected about all emails (incoming and outgoing) for a period of Oct 2003 to May 2005. Nodes represent email addresess and an edge between nodes i and j represents that i sent at least one email to j. The network contains 265214 nodes and 420045 edges and available from stanford.

Author Network: is a collaboration network of authors from the field of computational geometry. Two actors are connected to each other if they have co-authored an artifact together. The network was produced from the BibTeX bibliography obtained from the Computational Geometry Database 'geombib', version February 20024 . Problems with different names referring to the same person are manually fixed and the data base is made available by Vladimir Batagelj and Andrej Mrvar: Pajek datasets from the website5 . We only consider the biggest connected component containing 3621 nodes and 9461 edges.

All these five datasets model contextually and semantically different social relations from each other. Twitter network is a friend network and represents mutual acceptance from both individuals. Epinions network is similar in the sense that it requires mutual acceptance but differs as it requires a certain degree of trust rather than friendship. Wikipedia network is a directed network which represents the voting behavior of users to select administrators and is completely different from the previous two contexts. The fourth dataset is the Email network which is also a directed network where users are related to each other if a user has communicated to the other through email. Finally the Author network is an affiliation network [START_REF] Newman | The structure and function of complex networks[END_REF] which are based on bipartite graphs and are related to each other by having an affiliation to a common research artefact.

IV. N ETWORK S TATISTICS

Table I shows some basic network statistics calculated on the above described data sets. We briefly define these statistics below:

Density refers to the Edge-Node ratio of a network representing the average degree of a node in the network. Highest Degree (HD) is the highest node degree a node has in the network. Diameter is the number of edges on the longest path between any two nodes in the network. Girth of a graph is the path length of the shortest cycle possible. Clustering Coefficient Global (CCG) is the measure of connected triples in the network. Average Path Length (APL) is the average number of edges traversed along the shortest paths for all possible pairs of network nodes. Alpha(α) is the constant obtained when a power-law distribution is fitted on the degree distribution of the network.

Density values for Epinions and Wikipedia networks are comparatively very high representing high number of connections for each node in the network. High density of networks can be one reason for having high clustering coefficient for a network but in the presented datasets, the networks with the lowest density have the highest CCG values which represents an important structural trait for these network as they have slightly higher number of transitive triples. For the author network, this is inherent due to the construction method of the network as research artefacts with three or more than three authors will all form triads. This observation is more interesting for the email network where people exchange emails forming triads whereas relatively low values for the twitter network suggest that friend of a friend phenomena is not quite common when compared to the email network. Girth values of 3 for all these networks represents the presences of smallest possible cycle in the network.

The APL and α values of all the networks are quite close to each other again representing the similarity among the different networks. Low APL, High CCG and α values between 1.5 and 2 for twitter, email and author network represent the small world and scale free properties for these networks. The α value close to 1. Strength [START_REF] Auber | Multiscale visualization of small world networks[END_REF] is another group level metric which extends the notion of calculating triads in a network. This metric quantifies the neighborhood's cohesion of a given edge and thus identifies if an edge is an intra-community or an inter-community edge. The strength of an edge e = (u, v), s(e) is defined as follows:

str(e) = γ3,4 (e) γmax (e) where γ3,4 (e) is the number of cycles of size 3 or 4 the edge e belongs to and γmax (e) is the maximum possible number of such cycles. Using this edge strength, one can define the strength of a vertex as follows:

str(v) = e∈adj(v)
str(e) network show a linear decay in the degree distribution and should not be classified as scale free networks. The histogram of degree distribution for all these networks is presented in Figure 2.

V. N ETWORK M ETRICS

We use the following notation throughout this paper. A network is a graph G(V, E) where V is a set of nodes and E is a set of edges. u, v, w ∈ V represents nodes and e ∈ E represents an edge in the network.

In this section, we briefly describe a number of network metrics frequently used in network analysis. All the metrics considered are node level metrics or can be derived for nodes. Metrics are grouped together into Element Level Centrality, Group Level Cohesion and Network Level Centrality metrics. The metrics we have considered for experimentation are most widely used metrics in network analysis but the list is certainly not complete and an exhaustive study remains part of our future work.

A. Element Level Centrality Metrics

Element level metrics are calculated on individual elements of a graph, in this case for nodes. The term centrality refers to the idea where these elements are central in some sense in the graph.

Degree of node is an element level metric which refers to the number of connections a node has to other nodes. Degree distribution of nodes has been one of the most important metric of study for networks as the degree distribution of most real world networks follow power law [START_REF] Li | Towards a theory of scale-free graphs: Definition, properties, and implications[END_REF].

B. Group Level Cohesion Metrics

Group Level Metrics are metrics that are calculated for a small subset of nodes within the graph. The two metrics we consider here in our study are cohesion metrics that give a measure of how closely a group of nodes is connected to each other.

Local Clustering Coefficient [START_REF] Watts | Collective dynamics of 'small-world' networks[END_REF] is a group level metric which counts the degree of connectedness among neighbors of a node. Clustering coefficient for a node n, having kn edges which connects it to kn neighbors is given below:

2 * en cc(n) = kn * (kn -1) deg(v)
where adj(v) is the set of edges adjacent to u and deg(v) is the degree of v. The idea is to quantify whether the neighbors of a node connect well to each other or are loosely connected to each other. The values range between [0,1] such that low values indicate poor connection whereas high values indicate strong connections among the neighbors of a node.

C. Network Level Centrality Metrics

Network Level Metrics require the entire graph for calculation. Centrality in the context of network level metrics is a structure level metric which calculates how central a node is, in the entire network.

Betweenness Centrality [START_REF] Freeman | A set of measures of centrality based on betweenness[END_REF] calculates how often a node lies on the shortest path between any two pair of nodes in the network. Mathematically, the metric is defined as: bc(v) = u=v=w∈V µuw (v) µuw where µuw (v) equals the number of shortest paths between two nodes u and w ∈ V going through the node v and µuw equals the number of shortest paths between two nodes u and w ∈V.

High betweenness centrality for many nodes suggest that the entire network has pockets of densely connected nodes or communities. Low values of betweenness centrality suggest that nodes of the entire network are well connected to each other representing the absence of well defined boundary structure for communities.

Eccentricity [START_REF] Hage | Eccentricity and centrality in networks[END_REF] also tries to capture the notion of how central a node is in the network. The eccentricity ecc(v) of a node is the maximum distance between v and any other node u of G. Mathematically, eccentricity can be calculated by using the following equation:

High values of eccentricity for many nodes in the network represent that there are people connected through long chains in the network which pushes these individuals far from the dense core as described by Kumar et al. [START_REF] Kumar | Structure and evolution of online social networks[END_REF]. Three sampling methods exist in the literature for sampling graphs and networks. Node sampling, in which an induced sub graph of randomly drawn nodes is considered as a sample. Link sampling, in which randomly drawn edges are considered and their nodes are added to the network. And finally the most agreed upon sampling method for social networks [START_REF] Ahn | Analysis of topological characteristics of huge online social networking services[END_REF], the snowball sampling which starting from a seed node, performs a breadth-first search collecting a subset of the entire graph [START_REF] Rothenberg | Commentary: Sampling in social networks[END_REF].

ecc(v) = 1 max{d(v, u) : u ∈ V }
We used random repeated sampling collecting 10 samples of size 500 nodes from each data set giving us a total of 50 graphs. Next we calculated different network metrics on these samples. For each sample, we calculated the frequencies of the resulting values giving us a distribution of how these metric values occur in the network. For example, in case of the degree metric, we calculated the frequencies of the degree values obtained for the network. Next, for each data set we calculated the average of these frequencies. We then calculated the correlation coefficient of each sample from its average to give an idea of how much variation occurs in the sampled data.

Figure 1 clearly shows that closeness and eccentricity values for certain samples vary from the average values calculated for the respective data sets. For example closeness values for sample 2 and 4 for Email data, sample 2 and 9 for Epinions data, eccentricity values for sample 7 for Epinions, sample 8 for wiki and sample 5 and 8 for Author network have all very low values of correlation with the average values calculated for the respective samples. Both Eccentricity and Closeness are Network level metrics and represent how centric nodes are in a network. Eccentricity is the maximum distance a node can have from any other node, and Closeness is the average of the maximum distances from a node to all other nodes. Collecting a sample using snowball sampling is vulnerable with respect to both these metrics as the sampling method itself is based on generating paths from a seed node.

VII. I NFERENCES AND O BSERVATIONS

Figure 2 shows the frequency distribution calculated for the above described metrics. These metrics either return values between 0 and 1, or have been normalized in this range to facilitate comparative study. Furthermore we have applied binning to calculate frequencies where the values have been rounded off to 2 decimal places giving us bins in the range [0.00, 0.01, 0.02, • • • , 1.00]. The values on the horizontal axis for the graphs in Figure 2 represent the bin number, i.e. bin 0 refers to the frequency of nodes for the value 0.00, bin 1 refers to the value 0.01 and so on. One final modification to these graphs is that we have cut the extreme bins for Degree distribution, Strength, Betweenness Centrality and Closeness as there was very less information available in these bins.

From the degree distribution of the five networks in Figure 2 the graphs for the author and the twitter network are quite similar. The most interesting observations are for the wikipedia and the epinions network where we can see a linear decay in Closeness [START_REF] Beauchamp | An improved index of centrality[END_REF] is another network level metric which is the inverse sum of distances of a node to all other nodes given by the equation:

clo(v) = 1 {d(v, u) : u ∈ V }
Closeness of a node represent on average, how close or how far it lies from all other nodes in the network. These nodes are good candidates to spread information as individuals with low values representing people that are closely connected to all other nodes in the network.

VI. E XPERIMENTATION

As the first step to perform a comparative analysis of various networks using different metrics, we perform sampling on all these data sets to obtain equal size networks in terms of number of nodes. In order to verify whether our samples truly reflect the original network we conducted a simple experiment which itself revealed interesting results about sampling methods.

the degree distribution of the two networks which shows a nonscale free behavior of the two networks. The email network has a very high peak for very low values showing that most of the individuals in this network have used email very rarely for communication purposes.

The clustering coefficient frequencies have a similar behavior as all the networks have peaks in their frequency values. For example, the twitter network has a peak at bin 11 which refers to a value of 0.11. This shows that around 30 nodes have a clustering coefficient of 0.11. Other networks have a peak which starts from bin 21 to 51. The lowest peak is for the email network although the global clustering coefficient of this network is higher than other networks as shown in Table I. This suggests that the triads in the email network are not concentrated around nodes part of the core of the network but are well spread out in the whole network.

A similar observation can be made about the frequencies for the strength metric as values gradually rise and fall off for every dataset. Wikipedia and epinions networks have frequencies quite close to each other, the email network has its peak shifted on the right and twitter's peak shifted on the left. This means that the email network has more dense components of size 4 as compared to twitter network which does not have many such nodes.

Betweenness centrality has the most perfect match for all these networks. This is due to a few nodes with very high degree present in all networks. These nodes in turn play a central role in connecting short paths among pairs of nodes. This finding can be reinforced by the low APL values for all networks and the HD values shown in Table I.

Eccentricity values of different networks follow each other very closely. This is again an implication of the presence a few very high degree nodes in the network as the maximum distance among any pair of nodes does not vary much, as all nodes use these high degree nodes which act as short cuts in these networks.

The most variation in the behavior of frequencies is for the closeness metric. The email network has initially high values as opposed to other networks but remains very low for other values. This is because it has a node with exceptionally very high degree as it is connected to all other nodes. This reduces the average closeness of all pair of nodes. The twitter network has peaks around bin number 7, 27-28, 35 and 42 which is quite different from other networks. Wikipedia has also different peaks but they are shifted towards the right when compared to the twitter network, which signifies higher frequencies for high closeness values. Epionions has a peak around bin 24 which gradually decreases and the author network has its peak value at around bin 46.

In general, the behavior of all these networks is similar when evaluated with the discussed metrics. Two findings can be quoted, one for the non-scale free behavior of two social networks, epinions and wikipedia. Second is the variations in frequencies for the closeness metric. Both these results highlight the slight structural dissimilarity among different forms of social networks.

VIII. C ONCLUSION

In this paper, we have performed a comparative study to analyze contextually and semantically different social networks using different network statistics and metrics. Our results show that these network are structurally similar to each other in most of the cases. The comparative study selected one representative dataset from each form of social network, as we only consider only one friendship network and one email communication network. These results need to be generalized by considering other networks of the same form.

We also demonstrated that snowball sampling method is vulnerable against two network level centrality metrics, eccentricity and closeness as repeated sampling on different data sets revealed inconsistent behavior of these networks. As part of future work, we intend to incorporate more data sets and more network metrics to perform a comprehensive comparative analysis of different social networks. We also intend to explore the possibilities of proposing a new sampling method which is robust against different structural metrics.

Fig. 1 .

 1 Fig. 1. Calculating different Network Metrics on each sample of the Five datasets.

Fig. 2 .

 2 Fig.2. Calculating different Network Metrics on the Five datasets. Horizontal axis represents bins and vertical axis represents the frequency with which nodes appear in that particular bin.

  2 for epinions and wikipedia http://www.math.utah.edu/∼beebe/bibliographies.html 5 http://vlado.fmf.uni-lj.si/pub/networks/data/

		Twitter	Epinions	Wikipedia	Email	Author
	Nodes Edges Density HD Diameter Girth CCG APL α	500 3099 6.18 237 11 3 0.19 2.6 1.57	500 13739 27.47 278 7 3 0.43 1.93 1.202	500 11672 23.34 281 12 3 0.35 2.10 1.209	500 2396 4.79 499 7 3 0.54 1.98 1.87	500 2404 4.80 102 10 3 0.60 2.87 1.66

TABLE I BASIC

 I S TATISTICS FOR THE DATA S ETS USED IN E XPERIMENTATION . HD= H IGHEST N ODE D EGREE , CCG= C LUSTERING C OEFFICIENT G LOBAL , APL=AVG . PATH L ENGTH , α=P OWER L AW F ITTING C ONSTANT

api.twitter.com

http://www.epinions.com/

http://snap.stanford.edu/data/

see


B Varlot

Y Chembo

C Finot

Akhmediev breathers as ultra-wideband pulses

Keywords: nonlinear optics, ultra-wideband, fiber optics

We analytically calculate and discuss the radio-frequency spectrum of the socalled Akhmediev breathers, a class of nonlinear solutions of the nonlinear Schrodinger equation that governs the propagation in a single mode optical fiber. We propose a practical application of ABs to the field of ultra-wideband pulse generation.

Introduction

Solitons on finite background (SFB) are solutions of the nonlinear Schrödinger equation (NLSE) that are presently stimulating a renewed and widespread attention in nonlinear science. Even if their analytical expressions have been proposed for more than 25 years [START_REF] Kuznetsov | Solitons in a parametrically unstable plasma[END_REF][START_REF] Akhmediev | Modulation instability and periodic-solutions of the nonlinear Schrödinger equation[END_REF], these nonlinear structures have been only recently identified as promising prototypes of the infamous oceanic rogue waves [START_REF] Akhmediev | Waves that appear from nowhere and disappear without a trace[END_REF][START_REF] Onorato | Rogue Waves: From Nonlinear Schrödinger Breather Solutions to Sea-Keeping Test[END_REF]. Indeed, due to the periodic exchange of energy between a continuous background and a localized structure, an initially small perturbation can exponentially grow into a brief and intense spike before disappearing. With the emergence of the field of optical rogue waves, theoretical and experimental works have confirmed that optical fibers represent an ideal testbed to easily generate and study SFB : Peregrine soliton [START_REF] Hammani | Peregrine soliton generation and breakup in standard telecommunications fiber[END_REF], Akhmediev breathers (ABs) [START_REF] Hammani | Spectral dynamics of modulation instability described using Akhmediev breather theory[END_REF], or Kuznetsov-Ma (KM) solitons [START_REF] Kibler | Observation of Kuznetsov-Ma soliton dynamics in optical fibre[END_REF] have indeed been demonstrated taking advantage of widely available components for ultrafast optics. Connections with modulation instability [START_REF] Erkintalo | Higher-Order Modulation Instability in Nonlinear Fiber Optics[END_REF],

supercontinuum generation [START_REF] Dudley | Modulation instability, Akhmediev Breathers and continuous wave supercontinuum generation[END_REF] and generation of ultrashort structures [START_REF] Mahnke | Possibility of an Akhmediev breather decaying into solitons[END_REF][START_REF] Fatome | High-quality optical pulse train generator based on solitons on finite background[END_REF] have recently been suggested but at this stage, no solution has been designed to take advantage of the specific features of the SFB.

In this context, it sounds appealing to investigate the potential of Akhmediev breathers in the field of optical ultra-wideband pulse generation. Indeed, whereas the temporal intensity or phase profiles [START_REF] Hammani | Peregrine soliton generation and breakup in standard telecommunications fiber[END_REF][START_REF] Devine | Recurrence phase shift in Fermi-Pasta-Ulam nonlinear dynamics[END_REF], the associated optical spectra [START_REF] Hammani | Spectral dynamics of modulation instability described using Akhmediev breather theory[END_REF] or the longitudinal recurrence [START_REF] Devine | Recurrence phase shift in Fermi-Pasta-Ulam nonlinear dynamics[END_REF][START_REF] Van Simaeys | Experimental Demonstration of the Fermi-Pasta-Ulam Recurrence in a Modulationally Unstable Optical Wave[END_REF], have already been the subject of cautious theoretical and experimental works, the radio-frequency (RF) spectrum has not been exploited yet.

We analytically calculate in this contribution the RF spectrum of ABs and demonstrate that they exhibit an ultra-wideband spectrum whose central frequency depends on the system parameters. This letter will be organized as follows. After having recalled the specific features of ABs, we provide the analytical expression of their RF spectrum. The evolution of the central frequency of this spectrum according to the parameters of the AB is then discussed. Finally, we compare the RF spectrum of ABs with spectra of usual Gaussian singlets and doublets for practical application to ultra-wideband pulse generation.

Akhmediev breathers

The propagation of light in optical fibers is described by the NLSE :

2 2 2 2 || 22 i i i zt              (1)
where z and t denote the distance and retarded time (in the frame travelling at the group-velocity) coordinates; AB is a class of solutions of the NLSE whose general expression (neglecting a term of propagating phase) reads as :

    mod 0 mod (1 4 ) cosh( ) sinh( ) 2 cos ( , ) 2 cos cosh( ) a b i b b a t tP a t b           (2)
The parameters a and b are the normalized perturbation frequency and instability growth rate, and in dimensional units are given by   At the point of maximum compression (i.e. at 0   ), the compressed field is given by :

    mod 0 mod (1 4 ) 2 cos ( , 0) 2 cos 1 a a t tP at       (3)
We compare the temporal intensity profiles obtained for a selection of three values of a (0.25, 0.375 and 0.47). The value a = 0.25 leads to the maximum of gain of the modulation instability process whereas 0.47 represents the highest value of a that has been to date experimentally reported [START_REF] Hammani | Peregrine soliton generation and breakup in standard telecommunications fiber[END_REF]. The various examples are plotted on panels (1) of Fig. 1 (a = 0.25, 0.375 and 0.47 correspond to subplots a, b and c respectively). One can then clearly notice ultrashort and intense spikes of light lying over a continuous background as well as the increasing compression experienced for higher values of a .

The spectrum () s  of the AB (i.e. the Fourier transform of Eq. ( 2),  being the angular frequency) is well documented [START_REF] Hammani | Spectral dynamics of modulation instability described using Akhmediev breather theory[END_REF] and exhibits a typical triangular shape when plotted on a logarithmic scale, highlighting the decrease of the frequency components. Due to the intrinsic temporal periodicity of ABs, the resulting spectrum is a comb with the amplitude n s of the different frequency components given by [START_REF] Hammani | Spectral dynamics of modulation instability described using Akhmediev breather theory[END_REF] (here, factors of constant amplitude and phase are ignored): By stating

                    2 0 2 2 2 2 sinh cosh 1 cosh 2 cosh cosh 2 sinh cosh 2 cosh 2 n n i b b p b s ba b b a i b b p b s a ba                            (4)
          2 2 2 sinh cosh cosh 2 cosh cosh 2 2 i b b p b ba b b a a r q                , ( 5
)
one can rewrite Eq. ( 4) into the following form :

0 1 n n sr s r q        (6)
Results are illustrated on panels (2) of Fig. 1 with the optical spectra (i.e. the square of the various coefficients ( 6)) obtained for different values of a. The continuously decreasing amplitude of the s n coefficients is confirmed, with a spectral extent increasing with higher values of a. We can note that the specific value of a = 0.375 leads to a cancelling of the central spectral component of the field.

Radio frequency spectrum of ABs

The RF spectrum () S  of ABs (i.e. the Fourier transform of the square of Eq.

(2)) has been to date fully unexplored and can be derived from Eqs [START_REF] Hammani | Spectral dynamics of modulation instability described using Akhmediev breather theory[END_REF]

  2 2 2 1 2 Re 1 n n q S q r n r q              (7)
so that the overall envelope of the RF spectrum is given by :

    mod 2 2 2 mod 1 2 Re 1 q S q r r q                    (8)
The RF spectrums and the associated envelope corresponding to the fields investigated in the previous section are plotted on Fig. 2. Compared to the simple algebraic decay of the optical spectrum tails, the RF spectrum undergoes a more complex evolution with frequency. The most important feature that can be made out is that the RF spectrum does not exhibit a monotonic decrease with increasing frequency: the RF envelope of the ABs has a local maximum which frequency depends on the value of a. For a = 0.25, the maximum of the RF spectrum is located at / mod = 1, whereas for a = 0.375 and 0.47, the maximum is shifted to the second and fourth spectral components respectively.

One question that may arise is the influence of the propagation distance  . Figue 3(a) where the longitudinal evolution of the RF spectrum envelope for a = 0.47 is plotted outlines that the most significant shift is obtained at the point of maximum compression. From Eq. ( 8), one can evaluate more quantitatively the frequency  max at which the envelope is maximum :

2 max 2 mod 1 1 2 ln 1 q q q r         (9)
which can be simplified at the point of maximum of compression (where

2 1 2 ra  and 1 1 2 2 a a q  
) into :

      max mod 1 1 1 0 21 ln 2 / 2 ln 1 12 1 2 1 2 12 a aa a aa               (10)
Results are plotted in Fig. 3(b) and clearly points out that the central frequency continuously increases for increasing values of a.

Comparison with simple shapes of ultra-wideband pulses

The generation of an ultrashort pulse train with a maximum of the RF spectrum shifted towards high frequency is a feature of interest in the context of ultra-wideband pulse generation [START_REF] Jianping | Photonic Generation of Ultrawideband Signals[END_REF]. Indeed, as the experimental setup involved in the generation of ABs is remarkably simple and can be easily scaled to repetitions rates of several tens of GHz [START_REF] Hammani | Peregrine soliton generation and breakup in standard telecommunications fiber[END_REF], it is worthy to compare the performance of the AB with the spectra of widely used pulse trains such as Gaussian singlet or doublets.

We have therefore considered here an AB at the point of maximum compression with a value of a of 0.47. The resulting RF spectrum is compared on Fig. 4(a) with Gaussian singlets and doublets having the same central frequency. The RF spectrum of an AB is slightly broader compared with the singlet, but significantly larger than the spectrum of a doublet. Corresponding intensity profiles are compared on Fig. 4(b) and show that obtaining similar maximum frequencies of the RF spectrum requires a shorter structure in the case of an ABs. For the same average power, the ABs exhibits a higher peak level, so that the pulsed part better distinguishes from the continuous background.

Conclusions

We have analytically calculated the RF spectrum of ABs and highlighted a significant feature of the soliton over finite background: contrary to their optical spectrum, their RF spectrum does not exhibit a monotonic evolving shape and the location of the maximum of this spectrum can be directly related to the a parameter that takes both the fiber and light properties into account. To exploit this intrinsic property of the ABs can be of interest for ultra-wideband pulse generation. Even if the performance of this pulse shape does not seem to compare favorably with usual Gaussian singlets and doublets, the ease of implementation of the experimental generation may constitute an attractive architecture if very high repetition rates are targeted. The present discussion has been carried out in the context of passive fiber generation but breathers can also be observed in microresonators [START_REF] Matsko | On excitation of breather solitons in an optical microresonator[END_REF], paving the way to the all-optical and cost-effective generation on a compact optical chip. The proposed approach further stress all the benefits that can be obtained from the controlled shaping occurring in a medium presenting dispersion and Kerr nonlinearity [START_REF] Hammani | Nonlinear spectral shaping and optical rogue events in fiberbased systems[END_REF]. whereas the optical spectra (square of Eq. ( 4)) are displayed in panels 2.

Figure captions:

Time is normalized with respect to the period of the pulse train whereas frequency is normalized with respect to the repetition rate of the periodic signal. (black line) is compared with the analytical predictions of Eq. ( 7) (solid black circles) and with the envelope of the RF spectrum (grey solid line, Eq. ( 8)).

2 

 2 and  are the group velocity dispersion and the nonlinear Kerr coefficient, and ( , ) tz  is the field envelope. In order to simplify the discussion, it is interesting to introduce the normalized distance  related to the dimensional distance via /

  0.5, the value a = 0.5 leading to the solution known as the Peregrine soliton.

with 1 n

 1  and the parameter p being

Fig. 1

 1 Fig. 1 Train of optical breathers for different values of a : a = 0.25, 0.375 and 0.47 are plotted in panels a, b and c respectively. The temporal intensity profiles at the point of maximum compression (Eq. (3)) are plotted in panels 1

Fig. 2

 2 Fig. 2 RF spectra obtained for different values of a = 0.25, 0.375 and 0.47 (subplots a, b, c respectively). The numerical Fourier transform of Eq. (3)

Fig. 3 (

 3 Fig. 3 (a) Longitudinal evolution of the envelope of the RF spectrum for a = 0.47. (b) Evolution of the frequency of the maximum of the RF spectrum with respect to the parameter a at the point of maximum compression according to Eq. (10).

Fig. 4 (

 4 Fig. 4 (a) Comparison of the envelopes of the RF spectrum of a train of ABs (solid black line, a = 0.47) with the RF spectrum of a Gaussian singlet (dashdotted line) and Gaussian doublet (dashed grey line) having similar central frequencies. (b) Comparison of the corresponding temporal intensity profiles.

Figure 1 Figure 2

 12 Figure 1

Figure 3 Figure 4

 34 Figure 3

Acknowledgements:

We thank Kamal Hammani, Bertrand Kibler, Julien Fatome and G. Millot for stimulating discussions. We acknowledge the financial support of the Conseil Regional de Bourgogne (Pari Photcom) and the Agence Nationale de la Recherche (project SO FAST, ANR-11-EMMA-0005 and OPTIROC, ANR-12-BS04-0011). We also thank the funding of the Labex ACTION program (ANR-11-LABX-01-01).l