106 IEEE TRANSACTIONS ON VISUALIZATION AND COMPUTER

106 Ieee Transactions On Visualization And Computer-Free PDF

  • Date:01 Jul 2020
  • Views:2
  • Downloads:0
  • Pages:15
  • Size:1.64 MB

Share Pdf : 106 Ieee Transactions On Visualization And Computer

Download and Preview : 106 Ieee Transactions On Visualization And Computer


Report CopyRight/DMCA Form For : 106 Ieee Transactions On Visualization And Computer


Transcription:

CORREA ET AL VISUAL REASONING ABOUT SOCIAL NETWORKS USING CENTRALITY SENSITIVITY 107. Fig 1 Centrality sensitivity a Subnetwork of the genealogy of influence data set 25 b Plot of changes in centrality for some key nodes as the. degree of Russell changes We see that some nodes become less important while others improve The rate of change of these functions their. derivatives are the sensitivity parameters c We can color code the sensitivity red blue indicates negative positive influence to understand how. centrality is propagated for a change in a given node d A full visualization of the sensitivity parameters. eigenvector and Markov centralities 5 48 To better we end up with a pairwise matrix of sensitivities In Fig 1d. understand the notion of sensitivity and derivatives of we visualize the pairwise sensitivity between all connected. centrality let us analyze the problem for a small network nodes using the same color scheme Note that sensitivity is. in general not symmetric For example the sensitivity. 1 1 An Illustrative Example between Husserl and Frege is asymmetric. Consider the network depicted in Fig 1a a subset of a. network of intellectual influence among great thinkers in 1 2 Contributions. History 25 In this network of renowned artists mathe In this paper we provide an analytical mechanism for. maticians and philosophers a link is made if a person s computing sensitivities of centrality and show their. work has influenced the works of another We see this practical value for visual reasoning about social networks. subnetwork as a combination of a star network rooted by In particular we provide. Husserl and a cluster formed by the nodes on the right. including Russell Frege Godel and others To understand 1 a general strategy for computing the variation of. sensitivity we perform the following experiment Take the centrality as an analytical expression for eigenvector. node Russell and start increasing its degree Because there and Markov centralities and a numerical approx. are so many combinations that lead to the same increment imation for centrality functions in general. in degree let us assume that this change is stochastic In this 2 sensitivity overviews in node link diagrams as a. example we assume that all links incident to Russell have mechanism for characterizing and filtering complex. the same probability of 1 5 since there are five edges social networks. Then we start increasing all these edges by 1 5 then 2 5 3 a network simplification strategy that preserves the. and so on At each step we measure the centrality of all centrality distribution of the original network and. nodes The result is depicted in Fig 1b The x axis 4 a mechanism for assessing uncertainty in networks. represents the change in the weights associated to the and its application in understanding the robustness. edges incident to Russell and the y axis is centrality Each of network metrics. line corresponds to the centrality of one of the nodes in the The study of sensitivity in social networks is important to. cluster We clearly see that the changes applied to Russell characterize networks that are seemingly similar to under. have both positive and negative effects e g it boosts the stand the sources of variability in metrics such as centrality. centralities of James Bolzano Frege and Godel but also and to gain insight on the social dynamics of a network To. hinders the centralities of Husserl and Carnap Notice also the best knowledge of the authors this is the first. that in the latter case the impact is indirect since Russell variational study of social networks from the perspective. and Carnap are not directly connected Notice also that the of visualization. rate at which the change occurs is not uniform This rate the. derivative of those curves is the sensitivity of centrality. 2 RELATED WORK, and can be computed analytically for some centrality. functions as described in Section 3 2 1 Network Centralities. An example visualization of these derivatives is shown in The issue of centrality has been widely explored in. Fig 1c where color denotes the sign and strength of the numerous settings including sociometry biology and. sensitivity Red and blue links denote negative and positive information systems 43 One of the most obvious ways of. sensitivity respectively while the saturation of color in measuring centrality of a node is via its degree as first noted. dicates strength For example Frege s sensitivity to Russell is by Shaw 44 However this simple definition of centrality. smaller than that of James Dashed lines denote indirect may not suffice to capture the complex structural relation. sensitivities which occur between pairs of nodes not directly ships in a graph Harary and Hage 19 proposed a centrality. connected These are useful to visualize the region of based on eccentricity defined as the maximum distance of. influence of a node If we repeat the experiment for all nodes any node to other nodes in the network Other metrics are. 108 IEEE TRANSACTIONS ON VISUALIZATION AND COMPUTER GRAPHICS VOL 18 NO 1 JANUARY 2012. defined in terms of the total distance to other nodes in the these perturbations as changes in the degree of a node. network Nodes with small total distance are said to be Therefore the difference in centrality can be understood as. central Numerous closeness metrics have been proposed the partial derivative of the centrality with respect to the. including the information centrality and radiality of a node degree Naturally these derivatives can be combined to. For a closer look at these metrics refer to Jacob et al 28 and provide a bound although not necessarily tight of the. Newman s survey 38 stability of the centrality of a node A deeper analysis of the. Other more popular methods have been proposed for stability of centralities is performed by Koschu tzki et al 34. applications such as the analysis of social networks and. 2 2 Network Visualization, Website ranking These methods can be broadly categorized. as centralities based on shortest paths feedback and random The literature in network and graph visualization is. walks 7 The most common metric based on shortest paths extensive 13 One of the most widely studied topics is. is the betweenness centrality of a node introduced by the issue of graph layout Although force directed place. Anthonisse 2 and Freeman 14 as an alternative for ment is popular and easy to implement other more. closeness centrality in disconnected graphs Feedback sophisticated approaches have been proposed such as. based metrics define the centrality of a node in terms of GRIP 15 ACE 33 and FM3 18 To improve the. the centralities of other nodes Bonacich introduced a metric exploration of such networks a number of tools have. based on the eigenvectors of the adjacency matrix of a emerged such as yEd 26 GUESS 23 and JUNG 24. network 5 Before Bonacich Hubbell formulated the which provide a number of layouts overview detailed. problem in a similar fashion where the centrality of a node views magnifying glasses and color encoding of graph. is a linear combination of the centralities of others whose properties Heer and Boyd presented Vizster a system for. visualizing social networks 21 In addition to the cluster. solution can be found from the ensuing system of linear. ing effect of forced directed layouts they also provide an. equations 27 These feedback based methods became,explicit visualization of communities. more popular for Webpage indexing and are the core of. Recently there has been particular interest in guiding the. search algorithms such as PageRank 9 HITS 32 and, visualization of social and scale free networks using. SALSA 37 Unlike previous eigenvector centralities, centrality Perer and Shneiderman argue that an effective.
algorithms such as PageRank made the matrix stochastic. social network system must tightly couple statistics and. ensuring that the corresponding Markov chain converges to. visualization to provide a more effective exploration 42. a stationary distribution Finally the idea of using random. Brandes and Wagner discuss visone 8 a system for, processes to represent a network led to Markov centralities. visualizing social networks based on centrality which. as proposed by White et al 48 Their metric is defined as. includes layered and radial layouts similar to the Pajek. the mean first passage time of the Markov chain derived. system 3 To improve the layout of large graphs Girvan. from the adjacency matrix of the network,and Newman 16 propose edge filtering based on the. Several comparisons of these centrality metrics have. betweenness centrality of edges By removing the edges. been performed Freeman presents an exhaustive treatise of. with high BC they obtain simpler layouts that capture the. these methods in his seminal paper 14 Dwyer et al, structure of the network A similar approach was explored. performed a visual analysis to compare different centrality by van Ham and Wattenberg 46 The minimum spanning. metrics 12 They present a series of conventional visual tree retains these clusters When the highest BC edges are. analysis methods and hierarchical views to correlate the added back to the tree the result is a filtered but. centralities of nodes under different metrics Koschu tzki structurally meaningful network A different approach is. and Schreiber present a comparison of centrality measures taken by Jia et al 30 who used the highest BC edges to. for biological networks 35 Although no method was construct the tree They based their approach on the. particularly better than the others the authors recognized observation that scale free networks are mostly minimally. that each centrality method provided interesting insight on connected Using the highest BC nodes they extract the. how proteins interact communication channels that are most important in the. Inspired by these results we saw a need to understand network In our paper we show that centrality sensitivity. the behavior of centralities In this paper we extract also provides a ranking of the edges and that when used to. sensitivity as a visual quantity that helps users gain compute a minimum spanning tree the result maintains the. additional insight on the distribution and evolution of centrality of the important nodes This property is im. centrality metrics and consequently on the structure and portant to ensure the correct interpretation of a simplified. dynamics of the social network Similar studies have been network diagram. carried out to measure the sensitivity of centralities to small. perturbations in the network Langville and Meyer 36. studied the numerical stability of the eigenvector centrality 3 CENTRALITY SENSITIVITY. in the context of Web search Ng et al 40 were able to A graph G fV Eg consists of a set of nodes V and a set of. provide bounds of the difference magnitude between old edges E A node centrality is a function C V 7 R that. and new centralities after a perturbation These bounds assigns a real value to each node in V The larger the value. were later improved by Bianchini et al 4 In their study C v is the more important a node v is One of the simplest. they were concerned mostly with the stability of the ways to measure the centrality of a node is via its degree The. centrality vector given a perturbation in the network In degree of a node is the number of edges incident to that node. our paper we have a similar goal although we discriminate In a more general sense for weighted graphs we can define. CORREA ET AL VISUAL REASONING ABOUT SOCIAL NETWORKS USING CENTRALITY SENSITIVITY 109. the degree or valency of a node as the sum of weights of all C t1 t tn. the edges incident to that node Unweighted graphs are just a t 2. C t1 t h tn C t1 t tn, special case where the weight of an edge is 1 To this end it lim. becomes convenient to represent a graph via its adjacency. matrix A of size n n where n is the number of nodes Therefore the derivatives of centrality can be represented. For directed graphs it is often common to divide this as a matrix S where each element. metric as indegree and outdegree corresponding to the sums. of weights for incoming and outgoing edges of a node sij 3. respectively During our discussion we will derive central. ities in terms of the adjacency matrix regardless of whether encodes the sensitivity of node i with respect to node j To. the matrix denotes a directed or an undirected graph find an infinitesimal change in the centrality and therefore. We can see that the degree of a node is a somewhat local its derivative we observe that many centrality metrics are. metric of centrality Other measures such as betweenness algebraic operations on the adjacency matrix Therefore we. and eigenvector centralities as discussed below act can expand the derivative in terms of the derivatives of the. globally and the weights associated to the edges incident adjacency matrix using the chain rule of differentiation. to a node can potentially affect the centrality of other nodes C A dC A. throughout the network The measure of how much a node 4. can affect the centrality of others is called sensitivity within. where the derivative of the adjacency matrix is analogously. the context of sensitivity analysis 10 One mechanism for. computing sensitivity is via function derivatives 17 A t1 t tn. In a general sense sensitivity analysis explores the t. variation of a function in terms of the variation of its inputs 5. A t1 t h tn A t1 t tn, For social networks we can consider the centrality as a lim.
Visual Reasoning about Social Networks Using Centrality Sensitivity Carlos D Correa Member IEEE Tarik Crnovrsanin and Kwan Liu Ma Senior Member IEEE Abstract In this paper we study the sensitivity of centrality metrics as a key metric of social networks to support visual reasoning As centrality represents the prestige or importance of a node in a network its sensitivity represents

Related Books