Analysis of temporal networks Name: Chen Xi ID number: 15307130444 Abstract: The study of complex networks has been going on for many years. But because of the difficulty of getting a lot of data, most of people used to study static networks in early stage so that they ignored one of the important ariables, time. However, in recent years, time dimension has become an important aspect when researchers study on networks. This report is aimed to study the properties of temporal networks and the influence of the time windows by analyzing some properties of two datasets in a static way after dividing the whole network into some subnetworks (which are called slices in the following article) Key words: temporal networks, time windows, clustering coefficient, shortest distance, small world, periodicity 1 Introduction There are so many networks in our life will change over time such as interaction among people, the deployment of wiFi access in a campus and so on. So we have to consider an additional dimension-time when we want to do some dynamical research. Different from static networks, temporal networks are those networks whose structure may change over time, which means the edges between nodes may appear or disappear during the evolution. At present, the research of temporal networks mainly includes network modeling, statistical characteristics analysis, propagation dynamics and related human behavior analysis on such networks. And one of the biggest differences between temporal and static networks is that the edges between vertices of temporal networks need not be transitive In static networks, whether directed or not, if A is directly connected to b and b is directly connected to C, then a is indirectly connected to C via a path over B. However, in temporal networks, if the edge(A, B)is active only at a later point in time than the edge(B, c), then a and c are disconnected, as nothing can propagate from a via B to C, which shows the importance of time order So the study on temporal network usually conducted on the premise of time-respecting path, which means that paths are usually defined as sequences of contacts with non decreasing times that connect sets of vertices 2. And for further research, some chers use community structures to divide the temporal networks, or study the whole network without any division. However, when it comes to division, it's not easy to make time windows as small as possible to reduce the influence of time order and make sure there is only once interaction between two nodes in a time window. and in the next part, this report will count the number of interaction times as the weight of an edge between two nodes, which makes every slice a weighted network By calculating some properties of networks to compare the evolution in different time windows and analyze results in combination with reality. What's more, the report will compare the results of temporal networks with ER model networks to get more conclusions 2. Methods The two datasets of this report are from Hypertext 2009 dynamic contact network and Hospital contact network (fromhttp:/www.sociopatterns.org/datasets/).TheformeronewascollectedduringtheacmHypertext2009 conference. about 110 Conference attendees volunteered to wear radio badges that monitored their face-to-face roximity from 8: 00am on Jun 29th 2009. And the latter is a temporal network of contacts between patients, patients and health-care workers(HCWs) and among HC Ws in a hospital ward in lyon, France, from Monday, December 6 2010 at 1: 00 pm to Friday, December 10, 2010 at 2: 00 pm, which included 46 HCWs and 29 patients. They are tab- separated lists representing the active contacts during 20-second intervals of the data collection. Each line has the form"tij, where i and j are the anonymous IDs of the persons in contact, and the interval during which this contact
Analysis of temporal networks Name: Chen Xi ID number: 15307130444 Abstract: The study of complex networks has been going on for many years. But because of the difficulty of getting a lot of data, most of people used to study static networks in early stage so that they ignored one of the important variables, time. However, in recent years, time dimension has become an important aspect when researchers study on networks. This report is aimed to study the properties of temporal networks and the influence of the time windows by analyzing some properties of two datasets in a static way after dividing the whole network into some subnetworks (which are called slices in the following article) Key words: temporal networks, time windows, clustering coefficient, shortest distance, small world, periodicity. 1. Introduction There are so many networks in our life will change over time such as interaction among people, the deployment of WiFi access in a campus and so on. So we have to consider an additional dimension-time when we want to do some dynamical research. Different from static networks, temporal networks are those networks whose structure may change over time, which means the edges between nodes may appear or disappear during the evolution. At present, the research of temporal networks mainly includes network modeling, statistical characteristics analysis, propagation dynamics and related human behavior analysis on such networks. And one of the biggest differences between temporal and static networks is that the edges between vertices of temporal networks need not be transitive. In static networks, whether directed or not, if A is directly connected to B and B is directly connected to C, then A is indirectly connected to C via a path over B. However, in temporal networks, if the edge (A, B) is active only at a later point in time than the edge (B, C), then A and C are disconnected, as nothing can propagate from A via B to C, which shows the importance of time order [1] . So the study on temporal network usually conducted on the premise of time-respecting path, which means that paths are usually defined as sequences of contacts with nondecreasing times that connect sets of vertices [2] . And for further research, some researchers use community structures to divide the temporal networks, or study the whole network without any division. However, when it comes to division, it’s not easy to make time windows as small as possible to reduce the influence of time order and make sure there is only once interaction between two nodes in a time window. And in the next part, this report will count the number of interaction times as the weight of an edge between two nodes, which makes every slice a weighted network. By calculating some properties of networks to compare the evolution in different time windows and analyze results in combination with reality. What’s more, the report will compare the results of temporal networks with ER model networks to get more conclusions. 2. Methods The two datasets of this report are from Hypertext 2009 dynamic contact network and Hospital contact network (from http://www.sociopatterns.org/datasets/ ). The former one was collected during the ACM Hypertext 2009 conference. About 110 Conference attendees volunteered to wear radio badges that monitored their face-to-face proximity from 8:00am on Jun 29th 2009. And the latter is a temporal network of contacts between patients, patients and health-care workers (HCWs) and among HCWs in a hospital ward in Lyon, France, from Monday, December 6, 2010 at 1:00 pm to Friday, December 10, 2010 at 2:00 pm, which included 46 HCWs and 29 patients. They are tabseparated lists representing the active contacts during 20-second intervals of the data collection. Each line has the form “t i j”, where i and j are the anonymous IDs of the persons in contact, and the interval during which this contact
was active is [t-20s, t]. If multiple contacts are active in a given interval, there will be multiple lines starting with the same value of t All the analysis process was conducted in C language. Firstly, it should be emphasized that the temporal networks here are simplified without direction, which is called weak connectivity according to Nicolas's definitions two vertices i and j of a temporal network are defined to be strongly connected if there is a directed, time-respecting path connecting i to j and vice versa, while they are weakly connected if there are undirected time-respecting paths from i to j andj to i, i. e the directions of the contacts are not taken into account 1. This report focused on the evolution of one dataset and used different time windows such as 3 hours 6 hours. 12 hours. 24 hours and the whole network-48 hours, then counted the number of interaction times and regarded them as the weight of an edge between two nodes. After dividing the temporal network into above slices, there may be no interaction in some slices in a day so it should be deleted. And in order to keep the unity of two time agglomerations(two days in this report ), the corresponding slices in another day should also be deleted. Then the rest of the subnetworks could be regarded as some static networks to be analyzed. and this report mainly calculated the degree distribution, average degree(named strength"in weighted networks), average clustering coefficient(Ci -((k11)j=1 N wi and average shortest distance(Floyd algorithm) network)with p-0.1 and calculated the same properties of network and used the average to make a comparis e? Secondly, in order to search the relationship between temporal network and other network models, this repor counted the number of nodes and total weight in every slices, then put them into a er model network(also a weight Thirdly, this report used the methods above to analyze another dataset and kept the time windows same, which could make a comparison in different temporal networks and help researcher know more about the evolution of temporal networks in different time windows 3. Results After programming and processing data, the related results are as follows (1) Figure I and Figure 2 are average results of three properties of temporal network and ER model network different times windows. It shows that no matter what kind of dataset it is, the clustering coefficient in temporal network is far more than that value in ER model while the shortest distance has opposite result. And the average degree in two kinds of network is almost the same. Figure 3 is the curves of three properties in different time windows from 3 hours to 48 hours and the red curve represents network in ACM Hypertext conference and the blue one is the network in hospital Time windows Average degree Chustering coefficient Shortest distance 2742641792 0.007807417 3 hours 25600183 7.822216083 Temporal 006850667 6 hours m 50.50066533 0.0000145 1047694533 Temporal 70.3812325 0.004379 1457543 2 hours 0.0000175 10704636 Temporal 139.1617645 0.0086045 2.511026 24 hours ER model 20995049 253.261261 48 hours 2118591 ER model 253.261261 0.000035 25.792138 (Figure 1. ACM Hypertext
was active is [ t – 20s, t ]. If multiple contacts are active in a given interval, there will be multiple lines starting with the same value of t. All the analysis process was conducted in C language. Firstly, it should be emphasized that the temporal networks here are simplified without direction, which is called weak connectivity according to Nicolas ’s definitions: two vertices i and j of a temporal network are defined to be strongly connected if there is a directed, time-respecting path connecting i to j and vice versa, while they are weakly connected if there are undirected time-respecting paths from i to j and j to i, i.e. the directions of the contacts are not taken into account [3] . This report focused on the evolution of one dataset and used different time windows such as 3 hours, 6 hours, 12 hours, 24 hours and the whole network-48 hours, then counted the number of interaction times and regarded them as the weight of an edge between two nodes. After dividing the temporal network into above slices, there may be no interaction in some slices in a day so it should be deleted. And in order to keep the unity of two time agglomerations (two days in this report), the corresponding slices in another day should also be deleted. Then the rest of the subnetworks could be regarded as some static networks to be analyzed. And this report mainly calculated the degree distribution, average degree (named “strength” in weighted networks), average clustering coefficient(𝑐𝑖 = 1 𝑘𝑖∗(𝑘𝑖−1) ∑ ∑ (𝑤𝑖𝑗 𝑚𝑤𝑗𝑘 𝑚𝑤𝑖𝑘 𝑚) 1 𝑁 3 𝑘=1 𝑁 𝑗=1 ) and average shortest distance (Floyd algorithm). Secondly, in order to search the relationship between temporal network and other network models, this report counted the number of nodes and total weight in every slices, then put them into a ER model network (also a weighted network) with p=0.1 and calculated the same properties of network and used the average to make a comparison. Thirdly, this report used the methods above to analyze another dataset and kept the time windows same, which could make a comparison in different temporal networks and help researcher know more about the evolution of temporal networks in different time windows. 3. Results After programming and processing data, the related results are as follows: (1) Figure 1 and Figure 2 are average results of three properties of temporal network and ER model network in different times windows. It shows that no matter what kind of dataset it is, the clustering coefficient in temporal network is far more than that value in ER model while the shortest distance has opposite result. And the average degree in two kinds of network is almost the same. Figure 3 is the curves of three properties in different time windows from 3 hours to 48 hours. And the red curve represents network in ACM Hypertext conference and the blue one is the network in hospital. (Figure 1. ACM Hypertext)
Time windows Average degree Chustering coefficientShortest distance 81202251 006054667 3 hours ER model 15904426128333 3592305081 0.006454875 6.921292375 6 hours 111.753307 ER me 111.7533068 0.00002075 41.28081713 12 hours Temporal 198071539 0.0063875 392359275 ER model 1980715393 0.0000435 43.635674 24 hours Temporal319.4871795 0.0026135 3.5081905 model 3194871795 00001853 48.7788385 Temporal 52983871 844 5981 48 hours 52983871 0.000024 43.679006 Figure 2. Hospital) window (2)From Figure 4 to Figure 7 are the curves of average clustering coefficient and average shortest distance of every slice in different time windows(3h, 6h, 12h)of two datasets. The blue curves are results of temporal networks and the red curves belong to ER model networks. The X axis is the label of time slice and the Y axis is property. And when it comes to clustering coefficient, the blue curves are higher than red curves and they are undulate obviously. But it is totally opposite when it comes to shortest distance conference(3h) conference(6h conference(12h) 0012 0.003 系列1一系列2 系列1一系列2 系列1一系列2 (Figure 4. ACM Hypertext, clustering coefficient) conference(3h) time 一系列1一系列 系列1一系列2
(Figure 2. Hospital) (Figure 3. Time windows) (2) From Figure 4 to Figure 7 are the curves of average clustering coefficient and average shortest distance of every slice in different time windows (3h, 6h, 12h) of two datasets. The blue curves are results of temporal networks and the red curves belong to ER model networks. The X axis is the label of time slice and the Y axis is property. And when it comes to clustering coefficient, the blue curves are higher than red curves and they are undulate obviously. But it is totally opposite when it comes to shortest distance. (Figure 4. ACM Hypertext, clustering coefficient)
(Figure 5. ACM Hypertext, shortest distance) septal(3h) hospital(6h) hospital(12h) 05 105 time 系列1一系列2 系列2 系列1一系列2 (Figure6.Hospital,clustering coefficient) hospital(3h) hospital(12h 80 4 50 系列1一系列 al, shortest distance) ()From Figure 8 to Figure 1l are degree distribution of every slice in time window of 12 hours of two datasets just use this time window as an example to get the curve). And Figure 12 is the degree distribution in time window of 48 hours, which is the whole network in this research. As shown in the pictures, the fluctuation of curves is different in every slice but there is something common in two datasets. For example, in ACM conference, slice I and slice 3 are much more undulate than slice 2 and slice 4. There is the same result in Hospital dataset. conference(12h. 1) conference(12h. 2) 0045 IILA (Figure 8. ACM Hypertext, 12 hours)
(Figure 5. ACM Hypertext, shortest distance) (Figure 6. Hospital, clustering coefficient) (Figure 7. Hospital, shortest distance) (3) From Figure 8 to Figure 11 are degree distribution of every slice in time window of 12 hours of two datasets (just use this time window as an example to get the curve). And Figure 12 is the degree distribution in time window of 48 hours, which is the whole network in this research. As shown in the pictures, the fluctuation of curves is different in every slice but there is something common in two datasets. For example, in ACM conference, slice 1 and slice 3 are much more undulate than slice 2 and slice 4. There is the same result in Hospital dataset. (Figure 8. ACM Hypertext, 12 hours)
conference(12h. 3) conference(12h. 4) 5 04 0025 0.25 0015 0005 50100150200250300350 (Figure 9. ACM Hypertext, 12 hours) hospital(12h. 1) hospital(12h. 2) 007 006 0025 005 003 0005 ( Figure 10. Hospital, 12 hour hospital(12.3) hospital( 12h. 4) 045 0035 0025 0015 001 100200300400500600700800 100 300 500600 ( Figure 11. Hospital, 12 hours)
(Figure 9. ACM Hypertext, 12 hours) (Figure 10. Hospital, 12 hours) (Figure 11. Hospital, 12 hours)