K Hammani

C Finot

S Pitois

J Fatome

G Millot

Real time measurement of long parabolic optical similaritons

We generate long optical similaritons using a Raman fibre amplifier. These pulses, with a highly parabolic profile, are monitored in real time on a high speed oscilloscope. Tunability of both the temporal and spectral widths of the pulses is then investigated.

Introduction: Since their first experimental demonstration in 2000 [START_REF] Fermann | Self-similar propagation and amplification of parabolic pulses in optical fibers[END_REF], parabolic similaritons have stimulated a growing interest in the field of fibre amplification of high-power ultrashort pulses. This new type of optical pulse is asymptotically generated in an amplifier as the result of the combined interaction of normal dispersion, Kerr nonlinearity and gain. The pulse can then experience temporal and spectral self-similar dynamics and can evolve without suffering from the deleterious effects of optical wave-breaking which usually deteriorates the pulse shape propagating in the normal dispersion regime [START_REF] Dudley | Selfsimilarity in ultrafast nonlinear optics[END_REF].

Experimental demonstrations have been carried out both in rare-earth doped fibres (with Ytterbium [START_REF] Fermann | Self-similar propagation and amplification of parabolic pulses in optical fibers[END_REF] and Erbium [START_REF] Dudley | Selfsimilarity in ultrafast nonlinear optics[END_REF] dopants) as well as in Raman fibre amplifiers [START_REF] Finot | Numerical and experimental study of parabolic pulses generated via Raman amplification in standard optical fibers[END_REF]. The use of frequency resolved optical gating (FROG) technique based on iterative algorithms has enabled a precise but indirect intensity and phase characterisation of the amplified pulses which exhibit a parabolic intensity profile combined with a strictly linear chirp. Parabolic pulse durations ranging from 500 fs to 50 ps have then been demonstrated.

In this paper, we generate and characterise long (> 200 ps) parabolic pulses.

To this aim, the use of distributed Raman amplification is particularly well suited to adiabatically reshape initial picosecond-pulses into the targeted parabolic profile. Thanks to a 50-GHz high-speed oscilloscope coupled with an optical spectrum analyser, we have for the first time monitored in real time the parabolic pulse shape. We have also checked that the pulse duration and spectral width can be easily tuned over a wide range by simply adjusting the gain and the initial pulse energy.

Experimental set-up: The all-fibred experimental set-up is sketched in Fig. 1 and relies only on telecommunication-ready devices. Initial pulses are delivered by an erbium fibre laser working at a repetition rate of 22 MHz. The pulses are transform-limited with a temporal duration of 12 ps and a central wavelength of 1550 nm. They are amplified in a 15-km Raman amplifier based on a dispersion compensating fibre (normal dispersion β 2 = 16.6 10 -3 ps 2 /m and nonlinear coefficient γ = 4 /W/km). The amplifier is pumped by a continuous fibre laser with an output power up to 1 W. A counterpropagative pumping scheme is used in order to avoid deleterious temporal depletion effects [START_REF] Finot | Influence of the pumping configuration on the generation of optical similaritons in optical fibers[END_REF]. This also prevents from detrimental noise transfer from the pump to the signal so that the amplified pulse train exhibit very low amplitude and timing jitters as can be seen experimentally (insets Fig. 1) on a high-speed oscilloscope (50-GHz optical bandwidth). Output pulse spectra are also recorded.

Experimental results: Experimental results are summarised in Fig. 2 for a small signal gain of 28 dB (1 W pump) and for two values of the input pulse energy E ini (7.3 pJ, solid black line and 0.6 pJ, solid grey line). Experimental properties of input pulses are plotted in black dashed-line. Output intensity profile directly recorded by our high-speed photodiode (Fig. 2a) clearly illustrates the excellent agreement between the pulse shape (solid black line) and a parabolic fit (circles). From Fig. 2(a), we can make out that an increase in the initial pulse energy leads to an increase of the peak-power of the amplified pulse as well as its temporal duration, which is a signature of the intrinsic nonlinear nature of the self-similar pulse propagation. In contrast with the anomalous dispersion regime where the amplified shape is highly affected by solitonic compression effect, let us outline that the parabolic shape is here remarkably maintained over a wide range of input power.

The Kerr nonlinearity also leads to an enhanced spectral broadening as illustrated in Fig. 2b (a 15 time spectral broadening is recorded for a 7.2 pJ initial pulse energy). The spectra of the amplified pulse exhibit the characteristic shape of similariton pulses, i.e. rapidly decreasing wings combined with reduced oscillations in the central part of the pulse. Using a Gerchberg-Saxton algorithm [START_REF] Gerchberg R | A practical algorithm for the determination of the phase from image and diffraction plane pictures[END_REF] and given the temporal and spectral intensity profiles, one can infer the temporal chirp of the pulse. Results are plotted in Fig. 2c and highlight the high linearity of the chirp of the amplified pulses.

Given the ability to directly visualise the amplified pulses, we have studied the influence of the initial pulse energy E ini for different values of small-signal gain g. Temporal and spectral full-widths at half-maximum were recorded and results are plotted in Fig. 3. Output temporal width can be continuously varied over a wide range, from 50 ps to 250 ps. The experimental results are in good agreement with a fit based on a E ini 1/3 function which is typical of the selfsimilar analytical evolution of the parabolic pulses [START_REF] Fermann | Self-similar propagation and amplification of parabolic pulses in optical fibers[END_REF]. However let us note that for pulse durations below 100 ps, the asymptotic parabolic profile is not fully reached. The maximum temporal duration of 250 ps was only limited by the power available from the ps fiber laser so that larger temporal broadenings could potentially be achieved with more powerful seeds.

Whereas similar temporal broadenings can be obtained for pulses with initial energy of 3.6 pJ and 7.2 pJ associated with 28 dB and 18 dB gains respectively, the resulting spectral broadenings are rather different: pulses amplified in the 28 dB configuration are significantly more broadened than for the 18 dB configuration. This highlights that higher gains lead to pulses with a higher temporal chirp, which is qualitatively consistent with the g / β 2 expression of the linear chirp coefficient of the parabolic pulse [START_REF] Fermann | Self-similar propagation and amplification of parabolic pulses in optical fibers[END_REF].

Conclusion:

We have generated long 230-ps parabolic similariton pulses using an all-fibred device at telecommunication wavelengths. The parabolic profile has both been assessed by direct visualization on a 50-GHz oscilloscope and by monitoring the optical spectrum. The high quality of the temporal and spectral profiles will be a key element for future applications such as retiming processes [START_REF] Parmigiani | Pulse retiming based on XPM using parabolic pulses formed in a fiber Bragg grating[END_REF] or pulse shaping applications. Temporal and spectral properties of the similaritons can be instantaneously tuned over a wide range by simply adjusting the initial pulse energy or the Raman pump power.

Figure captions: Fig. 1 Fig. 2

 12 Figure captions:

Figure 1 Figure 2 Figure 3

 123 Figure 1

Acknowledgements: This research was supported by the Agence Nationale de la Recherche (SUPERCODE project, ANR-06-BLAN-0401) and by the Conseil Regional de Bourgogne. We thank J.M. Dudley for fruitful discussions.


Romain Bourqui
email: r.bourqui@tue.nl

Frédéric Gilbert
email: frederic.gilbert@labri.fr

Paolo Simonetto
email: paolo.simonetto@labri.fr

Faraz Zaidi
email: faraz.zaidi@labri.fr

† Umang
email: umangsh@gmail.com

Sharan ‡ Fabien
email: fabien.jourdan@toulouse.inra.fr

Detecting structural changes and command hierarchies in dynamic social networks

Community detection in social networks varying with time is a common yet challenging problem whereby efficient visualization of evolving relationships and implicit hierarchical structure are important task. The main contribution of this paper is towards establishing a framework to analyze such social networks. The proposed framework is based on dynamic graph discretization and graph clustering. The framework allows detection of major structural changes over time, identifies events analyzing temporal dimension and reveals command hierarchies in social networks. We use the Catalano/Vidro dataset for empirical evaluation and observe that our framework provides a satisfactory assessment of the social and hierarchical structure present in the dataset.

Introduction

Past work in social network analysis [START_REF] Wasserman | Social Network Analysis: Methods and Applications[END_REF] has shown that the knowledge of community structure and relationship strength has important applications in web analytics [START_REF] Chakrabarti | Enhanced hypertext categorization using hyperlinks[END_REF], marketing studies [START_REF] Domingos | Mining the network value of customers[END_REF] and homeland security [START_REF] Yang | Terrorism and crime related weblog social network: Link, content analysis and information visualization[END_REF][START_REF] Martinez | The soma terror organization portal (stop): Social network and analytic tools for the real-time analysis of terror groups[END_REF]. We can further improve our understanding of the social structure and changing roles within a network by exploiting the temporal evolution of relationships within the network. Social networks can exhibit temporal dynamics in a number of ways. The instances in the data may appear and disappear over time whereby different time windows may exhibit different characteristics. For example, various news web sites and blogs are dependent on the temporal events taking place globally. Moreover, the relationships in the data may represent events and associations that are significant at a particular point of time. If this is the case, then the time associated with these events should be modeled to capture important information. For example the time of a phone call just before a criminal activity in a terrorist network might indicate transmission of important information.

Community detection in social networks is of special interest to data mining researchers as it finds immediate application in marketing analytics, sociological and behavioral studies, etc. Previous work has focused on community detection through different clustering algorithms (Kmeans, agglomerative-hierarchical, etc) and summarization techniques [START_REF] Cortes | Communities of interest[END_REF]. For example [START_REF] Kang | Visual analysis of dynamic group membership in temporal social networks[END_REF] introduce a tool called C-Group for temporal analysis of social networks. The tool focuses on individuals rather than analyzing overall structural changes in the entire network. [START_REF] Gloor | Temporal visualization and analysis of social networks[END_REF] proposes a sliding time frame algorithm to display active ties between actors in a sliding time frame covering a time interval. The approach works well to trace the evolution of relationships between individuals but does not capture the community structure of the social network. Work has been done on discovering changing clusters in dynamic data [START_REF] Kalnis | On discovering moving clusters in spatio-temporal data[END_REF] and clustering evolving data streams [START_REF] Aggarwal | A framework for clustering evolving data streams[END_REF]. However, these techniques are either insufficient or inefficient to characterize the changes in community structure with time in an evolving network.

In this paper, we present a framework for intuitive visualization of changing communities over time. The main objectives are to identify the changing relationships in a social network through visualization, discover important events by observing any radical changes in the social structure and infer a role hierarchy (if present) by summarizing the social network dynamics.

We use the Catalano/Vidro data set for empirical evaluation of our framework [START_REF] Bourqui | Social Network Dynamics using Cellphone Call Patterns[END_REF]. The data set consists the information of 9834 telephone calls between 400 cellphones over a 10 day period in June 2006 in the Isla Del Sueno. The records provide critical information about the Catalano social network. The data set records each call as 5tuple (from user id, to user id, timestamp, call duration, cell tower location). We present the discussion in the next sections assuming the data set as a graph G = (V, E) where every edge e = (u, v) ∈ E represents a call between cell-phones u and v.

The rest of the paper is organized as follows: We present the proposed framework in section 2. The details of the decomposition algorithm and the network evolution measure are presented in sections 3 and 4. In section 5, we introduce a novel heuristic to determine the role hierarchy of the network. Finally in section 6, we present conclusions and directions for future research.

Framework

The given social network can be defined as a dynamic graph G described over a time period [0 . . . T ]. The proposed framework consists of four major steps which are briefly discussed below with details presented in the following sections.

In the first step, we convert the input social network and the corresponding dynamic graph G into a set of snapshot graphs. We decompose G into a sequence of static snapshots G [0,ǫ] , . . . , G [T -ǫ,T ] = G 1 , . . . , G n , where ǫ is the discretization factor and G [t,t+ǫ] is the static snapshot corresponding to the time period [t, t + ǫ] (i.e. the graph containing all vertices and edges involved during the time period [t, t + ǫ]). The value of ǫ is adjusted empirically and depends on the granularity of the time stamps present in the data set.

The second step clusters each static graph separately using an overlapping clustering algorithm, to produce Fuzzy Clusters. This step allows us to identify communities in the network but also its pivots (vertices shared by several clusters) while being insensitive to minor changes in the network.

The third step detects major structural changes in the network. We compare the clusterings obtained on every pair of successive static graphs using the similarity measure described in section 4. A low similarity indicates major changes during the period corresponding to these pair of snapshots while a high similarity value correspond to stable periods where the topological structure of the network does not go any major changes. Thus, once we have the similarity matrix from clusterings computed in step 2, we can decompose the temporal changes in the input network into periods of high activity and consensus communities during stable periods.

The last step consists of finding a role or influence hierarchy in the consensus communities filtered from step 3. We define the influence hierarchy as a tree G T = (V T , E T ) where V T ⊂ V is a subset of vertices in the input social network. The height of a node v ∈ V T represents the strength of influence of that node in the network. Our technique is based on the Delta efficiency metric [START_REF] Memon | Practical approaches for analysis, visualization and destabilizing terrorist networks[END_REF][START_REF] Memon | How investigative data mining can help intelligence agencies to discover dependence of nodes in terrorist networks[END_REF] which computes the importance of a vertex w.r.t the flow of information in the entire network. We use the Delta efficiency met-ric and Kruskal's algorithm [START_REF]On the shortest spanning subtree and the traveling salesman problem[END_REF] to infer the influence hierarchy in the network.

Graph decomposition

Strength metric

Our decomposition algorithm is based on the Strength metric, introduced by Auber et al. [START_REF] Auber | Multiscale Visualization of Small-World Networks[END_REF]. This metric quantifies the neighborhood's cohesion of a given edge and thus identifies if an edge is an intra-community or an intercommunity edge. The strength of an edge e = (u, v), w s (e) is defined as follows:

w s (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. Finally, one can define the strength of a vertex as follows:

w s (u) = e∈adj(u) w s (e) deg(u)
where adj(u) is the set of edges adjacent to u and deg(u) is the degree of u.

The time complexity to compute the strength metric over all vertices and edges is O(|E| • deg 2 max ) where deg max is the maximum degree of the graph.

Maximal independent set extraction

To identify the center of communities within the network, we use a method inspired by MISF 1 [START_REF] Gajer | GRIP: Graph dRawing with Intelligent Placement[END_REF] where we extract a maximal set ν of vertices such that ∀u, v ∈ ν,

dist G (u, v) ≥ 2.
The advantages of this algorithm are twofold: first, it gives the number of clusters with respect to the topology of the network and secondly, this technique guarantees the uniqueness of each found cluster (i.e. two clusters found by our approach cannot be identical) since a center can only belong to one cluster.

Notice that since the vertices in ν are the center of communities, these vertices should not be the pivots of the network as this may lead to over fitting a large community instead of several smaller communities. The network pivot nodes can be identified by low strength values as they are shared by several communities. Therefore, vertices with high strength values have to be added to the set ν.

To compute ν, we sort (in descending order) the vertices V according to their strength values as V ′ . Thereafter, we iterate over V ′ adding the top node to ν and removing it

Extracting communities

We use the high strength node set ν to extract communities from the input network. The main idea is to build balls with radius 1 around the vertices in ν. For each node u ∈ ν, if an edge (u, v) has a strength value higher than a given threshold τ , then this edge is considered as an intracluster edge and the node v is added to the community of u. The threshold τ is a function of the number of vertices and edges in the network. We consider several values for the threshold, τ 1 , .

Consensus structures

After the Graph decomposition step, we obtain n × m clusterings from the input network G-where n is the number of the snapshot graphs and m is the number of different values of a parameter τ applied during the graph construction or the graph decomposition. We denote the clustering set by C where each clustering C i,j corresponds to the decomposition of the graph G i with parameter τ j . As the decomposed graphs are naturally ordered w.r.t time, the most probable cluster evolution can be found by comparing each C i,j with each C i+1,k ∀i, j, k such that 1 ≤ i < n, 1 ≤ j, k ≤ m. We describe a similarity metric in the next section to evaluate the similarity between each pair of clusterings in C.

Similarity metric

The similarity metric aims to evaluate the similarity between two collections drawn over the same elements. It is related to the metric used in clustering protein-protein interaction networks [START_REF] Brohe | Evaluation of clustering algorithms for protein-protein interaction networks[END_REF]. The metric is based on the concept of representativeness. We say that a cluster c a ∈ C i,j is a good representative of a cluster c b ∈ C i+1,k if f c a contains a high ratio of the elements of c and a small ratio of elements not in c b . We define directed cluster representativeness as:

ρ ca→c b = c a ∩ c b / |c b | ρ c b →ca = c a ∩ c b / |c a |
which corresponds to the normalized ratio of the common elements between the two clusters. We further define the undirected cluster representativeness, or more simply cluster representativeness as:

ρ ca,c b = √ ρ ca→c b • ρ c b →ca
which corresponds to the geometrical mean of the direct representativeness of each cluster w.r.t the other.

Next, we extend the definition of cluster representativeness to groups of clusters or clusterings. We say that C i,j is a good representative of C i+1,k if the former contains a good representative cluster for each cluster in the latter. As small size clusters tend to bias the representativeness values, we give more importance to clusters representative of larger size clusters over smaller ones. We define the directed clustering representativeness as the weighted average (over the cardinality of the clustering) of the value of the best cluster representative found in C i,j for each cluster in C i+1,k :

σ Ci,j →C i+1,k = c b ∈C i+1,k max ca∈Ci,j ρ ca,c b • |c b | c b ∈C i+1,k |c b |
Similarly, we define the undirected clustering representativeness as the similarity metric:

σ Ci,j ,C i+1,k = √ σ Ci,j →C i+1,k • σ C i+1,k →Ci,j

Clustering Visualization

Under the hypothesis that cluster evolution presents an inertia towards drastic changes (that means that clusters do not change drastically at each time step), the similarity between different clusterings helps to identify a better parameter value τ . Currently, we are unable to select the optimal value τ j that gives us the best clustering result for the graph G i . Nevertheless, as a heuristic to estimate a good τ , we detect a sequence of clusterings C i,j , C i+1,k , C i+2,l . . . that has a higher similarity metric at each step than the average.

To study the behavior at two successive time steps, we calculate the maximum and the average similarity of two successive clusterings from σ Ci,j ,C i+1,k 1 ≤ j, k ≤ m. As described in the previous sections, if the difference between the maximum similarity and the average similarity values is large, this signifies radical changes in the network whereas if the difference is small, we can infer that no significant changes occurred in the network over time. This kind of analysis can be facilitated through a visual representation of the similarity metric value computation between the evolving clusterings. Figure 2 shows the similarity metric computation and network changes for the given data set. For each clustering C i,j , we add a node with coordinates (i, j) and add an edge corresponding to clusterings compared through the similarity metric with C i,j . These edges are then weighted with the similarity metric σ and graphically displayed using a varying color scale and/or varying edge thickness. Additionally, the maximum and the average values of the similarity metric at each time step is represented as a linear graph at the bottom as shown in figure 2.

Community Extraction

With time, communities can expand to include new nodes or merge with other communities or decrease in size by deleting nodes or splitting into subgroups. Thus, a community at a given time step might appear as two distinct groups either due to a previous split or a pending merge. To overcome this problem and obtain a global idea of the Thereafter, the consensus communities can be detected from the collection of matched clusters generated above. We use different filtering algorithms-union, intersection, fraction threshold-the optimal choice depends on the context and the properties of the input data set.

The computation of σ between two clusterings C i,j , C i+1,k is bounded by the computation of the intersection between each pair of cluster c a ∈ C i,j , c b ∈ C i+1,k . This step requires at most Q 2 |V | comparisons where Q is the maximum cardinality of C i,j and V is the number of nodes in the network. We have n time steps and m different clusterings for each time step. As each clustering C i,j is compared with all the clusterings at the following time steps, we calculate the similarity metric (n -1)m 2 times. Typically n and m are not very large-thus, the overall complexity is acceptable for an interactive computation. The calculation of the consensus communities depends on the filtering algorithm chosen by the user, but it is generally bounded by the computation of the similarity graph.

Influence hierarchy

In order to evaluate the measure of influence within a social network, we have to quantify the efficiency with which the nodes in the network exchange information. We use the idea of [START_REF] Latora | How Science of Complex Networks can help in developing Strategy against Terrorism[END_REF] to calculate this efficiency. We know that all nodes exchange information over a network represented by a graph G = (V, E), and this information can be picked by other nodes if required. For the given data set, each cell phone call represents such an exchange of information. The communication efficiency of the network ε ij between the nodes i and j is inversely proportional to the shortest path in the graph between i and j: ∀i, j ∈ V ε ij = 1/d ij , where d ij is the shortest path between i and j. If there is no path between i and j, then d ij = +∞ and ε ij = 0. We can quantify the efficiency of the whole network be calculating ε ij for each and every pair of nodes. The average efficiency of the graph G can be defined as:

Ef f (G) = i =j∈V ε ij / |V | • (|V | -1)
This metric gives us the communication efficiency of the network. To find a hierarchy in the network, we need to evaluate the efficiency or the criticality of each node as proposed by [START_REF] Latora | How Science of Complex Networks can help in developing Strategy against Terrorism[END_REF]. The idea is that if an important member of the network is removed, the efficiency of the graph should decrease, and vice versa. We define the Delta Efficiency(DE) of a node as:

I(node i ) = ∆Ef f i = Ef f (G) -Ef f (G\{i})
From a social point of view, we know that there are three kinds of roles in a network-the leaders, who are the thinking heads; the gatekeepers, who control the diffusion of information within the network and the followers who just execute orders. The ones that have the largest activity within the network are the gatekeepers and therefore, they have the highest DE values. On the other side, leaders and followers have very restricted communications (leaders just issue orders while followers receive/execute orders) which is the reason why they have very low DE values. Past work has shown that leaders try to hide themselves among followers [START_REF] Memon | Practical approaches for analysis, visualization and destabilizing terrorist networks[END_REF][START_REF] Memon | How investigative data mining can help intelligence agencies to discover dependence of nodes in terrorist networks[END_REF] (due to low DE values for both) to escape detection. One of the primary goals in hierarchy detection is to distinguish between followers and leaders. Since there are three roles that constitute a hierarchy in the social network, we do this by finding a tree representing this hierarchy such that it reveals the leaders and the followers.

Our inspiration comes from the fact that the edges of this tree must be part of the input social network. We know that the gatekeepers (right hands) of the leaders (boss) are the most critical nodes in the hierarchy. By definition, they are very close to the leader nodes in the network. We infer the hierarchy by using the spanning tree of the modified network where each edge is weighted by the importance of the relationship between the two nodes using DE as the importance metric. Thereafter, we classify the different role types within the influence hierarchy computed from the spanning tree.

Determining the spanning tree

We associate a weight with each edge between two nodes that is the difference between the DE value of the connected nodes. A high difference between DE values indicate that the two connecting nodes should not be placed on the same level in the hierarchy so the edge between these nodes can be removed. We take the absolute value that is inversely proportional to value associated to the edges as the edge weights for Kruskal's Minimum Spanning Tree algorithm to compute the hierarchy tree.

Inferring the hierarchy

Once we have the spanning tree, the next step is to find the leaders (boss) in the network. We know that the boss has a low DE value as he tries to hide himself by communicating less in the network and that he is in the neighborhood of the gatekeepers (right hands). [START_REF] Latora | How Science of Complex Networks can help in developing Strategy against Terrorism[END_REF] suggests that these right hands have the highest DE values in the network. But it may not be true that all the highest valued nodes are the right hands of the boss. To find the correct number of right hands of the boss we use a heuristic value of 3% that worked well for the input data set. Future work would involve calculating an optimal threshold value for the highest valued nodes. The idea behind finding the boss is that we take the 3% nodes having the highest DE value and construct a separate neighborhood list for each of these nodes which contains their immediate neighbors. Once we have these lists, we count the number of times the elements that appear in both the lists by taking two lists at a time. For example consider two node lists list 1 and list 2 that have 3 elements that are present in both of these lists. We add a value 1 as count to each of these elements. We repeat this process for all the possible combinations of the lists and at the end we come up with the node that is being communicated the most by the right hands. This node is probably the boss of the network as we know that the boss communicates a lot with his right hands. In case if two or more nodes have the same count, we take the node the lower DE value as we know that the boss does not have a high DE value.

Once we have a spanning hierarchical tree and the boss of the hierarchy, we adjust the orientation of the tree, starting from the root (boss) to have an ordered hierarchy. Given the complexity of our naive implementation of DE O((n + 1)(m + n 2 )) and the complexity of algorithm 1 is O(n 4 ), the overall worst-case complexity is O(n 4 ). In practice, however, the algorithm performs better than the worst-case.

Conclusion

In this paper, we have presented a framework to analyze dynamic social networks to detect structural changes over a time period based on graph discretization and temporal clustering. We have also presented a method to discover influence hierarchy in social networks using communication efficiency and minimum spanning tree algorithm. We have applied our framework on the Catalano/Vidro data set and obtained satisfactory results and we were able to correctly identify the time frames where major structural changes occurred as well as discover the influence hierarchy of the Catalano/Vidro family hidden in the input social network based on cell phone calls.

There are several details that we would like to address as part of future research to improve the overall framework like automatically picking the optimal discretization factor ǫ, optimal selection of the filtering threshold, etc. We have tested our framework on a single data set and we would like to extend the experimentation on other datasets as well.

Figure 1 .

 1 Figure 1. Framework overview

Figure 2 .

 2 Figure 2. Similarity graph of the Catalano/Vidro network with maximum and average similarity at bottom. Major changes occurred between steps 2 and 3 and minor changes between steps 8 and 9

  We skip the proofs of complexity in this paper due to lack of space.

. . , τ m obtaining m different clusterings at each time stamp. The time complexity of the communities extraction is O(|E|) and its space complexity O(|V | + |E|). The overall complexity of our decomposition algorithm is O(|E| • deg 2 max + |V | • log(|V |)) in time and O(|V | + |E|) in space.

  Input: A graph G = (V, E), DE n.∆ of each vertex n, the spanning tree T Output: The root node boss of the hierarchy and an orientation of the spanning tree T int number of nodes = 3 / 100 x |V | ; Sort(V , rule >, ∆) ; for i from 1 to number of nodes do

	table neighborhood = V [i].getNeighborhood ;
	for j from 1 to neighborhood.size do
	M [i][j] = neighborhood[j];
	end
	end
	list result;
	for i from 1 to number of nodes -1 do
	for j from (i + 1) to number of nodes do
	for k from 1 to M [i].size do
	for l from 1 to M [j].size do
	if( M[i][k] == M[j][l]) then
	result.push(M[i][k]) ;
	end
	end
	end
	end
	sort(result, rule >, nodes id) ;
	node boss = maxTimeAppears(result) ;
	makeOrientedTree(T , boss) ;
	Algorithm 1: Inferring the network hierarchy.