Graph Element Analysis图形元素的分析.ppt
《Graph Element Analysis图形元素的分析.ppt》由会员分享,可在线阅读,更多相关《Graph Element Analysis图形元素的分析.ppt(42页珍藏版)》请在三一办公上搜索。
1、Graph Element Analysis,Woochang HwangDepartment of Computer Science and Engineering State University of New York at Buffalo,IntroductionReal World NetworksCentralitiesMotivationBridging CentralityBridge CutDiscussionFuture Works,Introduction,Many real world systems can be described as networks.Socia
2、l relationships:e.g.collaboration relationships in academic,entertainment,business area.Technological systems:e.g.internet topology,WWW,or mobile networks.Biological systems:e.g.regulatory,metabolic,or interaction relationships.Almost all of these real world networks are Scale-free.,Real World Netwo
3、rks,Yeast PPI network,Real World Networks,Proteom Size(PDB),Real World Networks,Power law degree distribution:Rich get richerSmall World:A small average path lengthMean shortest node-to-node pathCan reach any nodes in a small number of hops,56 hopsRobustness:Resilient and have strong resistance to f
4、ailure on random attacks and vulnerable to targeted attacksHierarchical Modularity:A large clustering coefficientHow many of a nodes neighbors are connected to each otherDisassortative or AssortativeBiological networks:disassortativeSocial networks:assortative,Real World Networks,E.Ravasz et al.,Sci
5、ence,2002,Real World Networks,Protein Networks,Metabolic Networks,Real World Networks,Complex systems maintain their basic functions even under errors and failures(cell mutations;Internet router breakdowns),Real World Networks,Robust.For 3,removing nodes does not break network into islands.Very resi
6、stant to random attacks,but attacks targeting key nodes are more dangerous.,Max Cluster Size,Path Length,Centralities,Degree centrality:number of direct neighbors of node v where N(v)is the set of direct neighbors of node v.Stress centrality:the simple accumulation of a number of shortest paths betw
7、een all node pairs where st(v)is the number of shortest paths passing through node v.,Centralities,Closeness centrality:reciprocal of the total distance from a node v to all the other nodes in a network(u,v)is the distance between node u and v.Eccentricity:the greatest distance between v and any oth
8、er vertex,Centralities,Shortest path based betweenness centrality:ratio of the number of shortest paths passing through a node v out of all shortest paths between all node pairs in a networkst is the number of shortest paths between node s and t and st(v)is the number of shortest paths passing on a
9、node v out st Current flow based betweenness centrality:the amount of current that flows through v in a networkRandom walk based betweenness centrality,Centralities,Markov centrality:values for nodes show which node is closer to the center of mass.More central nodes can be reached from all other nod
10、es in a shorter average time.where the mean first passage time(MFPT)msv in the Markov chain and n is|R|,R is a given root set.where n denotes the number of steps taken and denotes the probability that the chain starting at state s and first returns to state t in exactly n steps.,Centralities,Informa
11、tion centrality:incorporates the set of all possible paths between two nodes weighted by an information-based value for each path.where with Laplacian L and J=11T,and is the element on the sth row and sth column in CI.It measures the harmonic mean length of paths ending at a vertex s,which is smalle
12、r if s has many short paths connecting it to other vertices.Random walk based closeness centrality is equivalent to information centrality,Centralities,Eigenvector centrality:a measure of importance of nodes in a network using the adjacency and eigenvector matrices.where CIV is a eigenvector and is
13、an eigenvalue.Only the largest eigenvalue will generate the desired centrality measurement.Hubbel Index,Katz status index,etc.,Centralities,Bargain Centraity:In bargaining situations,it is advantageous to be connected to those who have few options;power comes from being connected to those who are po
14、werless.Being connected to powerful people who have many competitive trading partners weakens ones own bargaining power.where is a scaling factor,is the influence parameter,A is the adjacency matrix,and is the n-dimentional vector in which every entry is 1.,Centralities,PageRank:link analysis that s
15、cores relatively importance of web pages in a web network.The PageRank of a Web page is defined recursively;a page has a high importance if it has a large number of incoming links from highly important Web pages.PageRank also can be viewed as a probability distribution of the likelihood that a rando
16、m surfer will arrive at any particular page at certain time.Hypertext Induced Topic Selection(HITS),etc.,Centralities,Subgraph centrality:accounts for the participation of a node in all sub graphs of the network.the number of closed walks of length k starting and ending node v in the network is give
17、n by the local spectral moments k(v).,Observation,Scale-free networks,basic properties Power law degree distributionSmall WorldRobustnessHierarchical ModularityDisassortative or AssortativeThere should be some bridging nodes/edges between modules in scale-free networks based on these observations,an
18、d we did recognize the bridging nodes/edges by visual inspection of small example networks.Finding the bridging nodes/edges,which are locating between modules,is an interesting and important problem for many applications on many different fields.(Networks robustness,paths protection,effective target
19、s finding,etc.),Motivation,Existing measurements are not enough for identifying the bridging nodes/edges:those existing indices are dominated by degree of the node of interest.Betweenness of an edge also have a strong inclination to attach onto high degree nodes.High tendency of cluttering in the ce
20、nter of the network.So,it is hard to differentiate the bridging nodes/edges from other kinds of nodes/edges.Our focus in this research is to target vulnerable and central components in a network from a totally different point of view.,Bridge,BridgeA bridge should be located on an important path,e.g.
21、shortest path.A bridge should be located between modules.The neighbor regions of a bridging node should have low range of public domain among them.,Betweenness and Bridging Coefficient,Betweenness:global importance of a node/edge from shortest paths viewpoint.Bridging Coefficient:a measurement that
22、measuring the extent how well a node or edge is located between well connected regions.the average probability of leaving the direct neighbor sub-graph of a node v.,Bridging Coefficient,Figure 1.Bridging Coefficient,Bridging Centrality,Bridging Centrality is defined as the product of the rank of the
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- Graph Element Analysis图形元素的分析 Analysis 图形 元素 分析
链接地址:https://www.31ppt.com/p-2783815.html