7.3 Strength of the ties It has been observed by Albert et al. 1 that many real world networks are robust to node-level changes or attacks Researchers have showed that networks like the World wide Web, Internet, and several social networks display a high degree of robustness to random node removals, i. e, one has o remove many nodes chosen uniformly at random to make the network disconnected. On the contrary, targeted attacks are very effective. Removing a few high degree nodes can have a dramatic influence on the connectivity of a network Let us now study how the Messenger communication net work is decomposed when"strong, "i. e, heavily used, edges are removed from the network We consider several different definitions of"heavily used, "and measure the types of edges ◆奢 that are most important for network connectivity. We note that a similar experiment was performed by Shi et al [13 Figure 17: Relative size of the largest connected in the context of a small Im buddy network. The author component as a function of number of nodes re- of the prior study took the number of common friends at moved the ends of an edge as a measure of the link strength. A the number of edges here is too large(1.3 billion)to remove edges one by one, we employed the following procedure: We order the nodes by decreasing value per a measure of the intensity of engagement of users; we then delete nodes as- sociated with users in order of decreasing measure and we bserve the evolution of the properties of the communication network as nodes are deleted We consider the following different measures of engage- -e- Avg sent Average sent: The average number of sent messages per users conversation Average time: The average duration of user's conver- 日= Random sations Links: The number of links of a user(node degree) i. e, number of different people he or she exchanged Figure 18: Number of removed edges as nodes are messages with deleted by order of different measures of engage- Conversations: The total number of conversations of a lel user in the observation period Sent messages: The total number of sent messages by time per conversation, average number of sent messages, or a user in the observation period number of sent messages per unit time. We were not sur- Sent per unit time: The number of sent messages per prised to find that the size of the largest component size de- unit time of a conversation creases most rapidly when nodes are deleted in order of the e Total time. The total conversation time of a user in decreasing number of links that they have, i. e the number the observation period of people with whom a user at a node communicates. Ran- dom ordering of the nodes shrinks the component at the At each step of the experiment, we remove 10 million slowest rate. After removing 160 million out of 180 million nodes in order of the specific measure of engagement being nodes with the random policy, the largest component still studied. We then determine the relative size of the largest contains about half of the nodes. Surprisingly, when deleting connected component, i. e, given the network at particu- p to 100 million nodes, the average time per conversation lar step, we find the fraction of the nodes belonging to th neasure shrinks the component even more slowly than the largest connected component of the network random deletion policy. Figure 17 plots the evolution of the fraction of nodes in Figure 18 displays plots of the number of removed edges the largest connected component with the number of deleted from the network as nodes are deleted. Similar to the rela- nodes. We plot a separate curve for each of the seven dif- tionships in Figure 17, we found that deleting nodes by the ferent measures of engagement. For comparison, we also inverse number of edges removes edges the fastest. As in consider the random deletion of the node Figure 18, the same group of node ordering criteria(num- The decomposition procedure highlighted two types of dy ber of conversations, total conversation time or number of namics of network change with node removal. The size of the sent messages)removes edges from the networks as fast as largest component decreases rapidly when we use the number of links criteria. However, we find that ran- sures of engagement the number of links, number of conver dom node removal removes edges in a linear manner. Edges sations, total conversation time, or number of sent messages. re removed at a lower rate when deleting nodes by aver- In contrast, the size of the largest component decreases very age time per conversation, average numbers of sent mes- slowly when we use as a measure of engagement the average sages, or numbers of sent messages per unit time. We be-7.3 Strength of the ties It has been observed by Albert et al. [1] that many real￾world networks are robust to node-level changes or attacks. Researchers have showed that networks like the World Wide Web, Internet, and several social networks display a high degree of robustness to random node removals, i.e., one has to remove many nodes chosen uniformly at random to make the network disconnected. On the contrary, targeted attacks are very effective. Removing a few high degree nodes can have a dramatic influence on the connectivity of a network. Let us now study how the Messenger communication net￾work is decomposed when “strong,” i.e., heavily used, edges are removed from the network. We consider several different definitions of “heavily used,” and measure the types of edges that are most important for network connectivity. We note that a similar experiment was performed by Shi et al [13] in the context of a small IM buddy network. The authors of the prior study took the number of common friends at the ends of an edge as a measure of the link strength. As the number of edges here is too large (1.3 billion) to remove edges one by one, we employed the following procedure: We order the nodes by decreasing value per a measure of the intensity of engagement of users; we then delete nodes as￾sociated with users in order of decreasing measure and we observe the evolution of the properties of the communication network as nodes are deleted. We consider the following different measures of engage￾ment: • Average sent: The average number of sent messages per user’s conversation • Average time: The average duration of user’s conver￾sations • Links: The number of links of a user (node degree), i.e., number of different people he or she exchanged messages with • Conversations: The total number of conversations of a user in the observation period • Sent messages: The total number of sent messages by a user in the observation period • Sent per unit time: The number of sent messages per unit time of a conversation • Total time: The total conversation time of a user in the observation period At each step of the experiment, we remove 10 million nodes in order of the specific measure of engagement being studied. We then determine the relative size of the largest connected component, i.e., given the network at particu￾lar step, we find the fraction of the nodes belonging to the largest connected component of the network. Figure 17 plots the evolution of the fraction of nodes in the largest connected component with the number of deleted nodes. We plot a separate curve for each of the seven dif￾ferent measures of engagement. For comparison, we also consider the random deletion of the nodes. The decomposition procedure highlighted two types of dy￾namics of network change with node removal. The size of the largest component decreases rapidly when we use as mea￾sures of engagement the number of links, number of conver￾sations, total conversation time, or number of sent messages. In contrast, the size of the largest component decreases very slowly when we use as a measure of engagement the average 0 2 4 6 8 10 12 14 16 x 107 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 Deleted nodes Component size Avg. sent Avg. time Links Conversations Sent messages Sent per unit time Total time Random Figure 17: Relative size of the largest connected component as a function of number of nodes re￾moved. 0 2 4 6 8 10 12 14 16 x 107 0 2 4 6 8 10 12 14 x 108 Deleted nodes Deleted edges Avg. sent Avg. time Links Conversations Sent messages Sent per unit time Total time Random Figure 18: Number of removed edges as nodes are deleted by order of different measures of engage￾ment. time per conversation, average number of sent messages, or number of sent messages per unit time. We were not sur￾prised to find that the size of the largest component size de￾creases most rapidly when nodes are deleted in order of the decreasing number of links that they have, i.e., the number of people with whom a user at a node communicates. Ran￾dom ordering of the nodes shrinks the component at the slowest rate. After removing 160 million out of 180 million nodes with the random policy, the largest component still contains about half of the nodes. Surprisingly, when deleting up to 100 million nodes, the average time per conversation measure shrinks the component even more slowly than the random deletion policy. Figure 18 displays plots of the number of removed edges from the network as nodes are deleted. Similar to the rela￾tionships in Figure 17, we found that deleting nodes by the inverse number of edges removes edges the fastest. As in Figure 18, the same group of node ordering criteria (num￾ber of conversations, total conversation time or number of sent messages) removes edges from the networks as fast as the number of links criteria. However, we find that ran￾dom node removal removes edges in a linear manner. Edges are removed at a lower rate when deleting nodes by aver￾age time per conversation, average numbers of sent mes￾sages, or numbers of sent messages per unit time. We be-