第321行: |
第321行: |
| | | |
| 普莱斯模型过于简单,不可能成为引文网络的现实模型,但它足够简单,可以为其某些属性提供分析解。其中许多问题可以通过使用从价格模型(Barabási-Albert 模型)的无向版本得出的结果来找到。然而,由于 Price 的模型给出了一个有向无环图,所以在寻找有向无圈图所特有的性质的解析计算时,它是一个很有用的模型。比如说, | | 普莱斯模型过于简单,不可能成为引文网络的现实模型,但它足够简单,可以为其某些属性提供分析解。其中许多问题可以通过使用从价格模型(Barabási-Albert 模型)的无向版本得出的结果来找到。然而,由于 Price 的模型给出了一个有向无环图,所以在寻找有向无圈图所特有的性质的解析计算时,它是一个很有用的模型。比如说, |
− |
| |
− | === Causal structures ===
| |
− |
| |
− | {{main|Bayesian network}}
| |
− |
| |
− | Graphs in which vertices represent events occurring at a definite time, and where the edges are always point from the early time vertex to a late time vertex of the edge, are necessarily directed and acyclic. The lack of a cycle follows because the time associated with a vertex always increases as you follow any [[Path (graph theory)|path]] in the graph so you can never return to a vertex on a path. This reflects our natural intuition that causality means events can only affect the future, they never affect the past, and thus we have no [[causal loop]]s. An example of this type of directed acyclic graph are those encountered in the [[Causal sets|causal set approach to quantum gravity]] though in this case the graphs considered are [[#Transitive closure and transitive reduction|transitively complete]]. In the version history example, each version of the software is associated with a unique time, typically the time the version was saved, committed or released. For citation graphs, the documents are published at one time and can only refer to older documents.
| |
− |
| |
− |
| |
− |
| |
− | Sometimes events are not associated with a specific physical time. Provided that pairs of events have a purely causal relationship, that is edges represent [[causality|causal relations]] between the events, we will have a directed acyclic graph.<ref>{{citation|title=Causal Learning|first1=Alison|last1=Gopnik|first2=Laura|last2=Schulz|publisher=Oxford University Press|year=2007|isbn=978-0-19-803928-0|page=4|url=https://books.google.com/books?id=35MKXlKoXIUC&pg=PA4}}.</ref> For instance, a [[Bayesian network]] represents a system of probabilistic events as vertices in a directed acyclic graph, in which the likelihood of an event may be calculated from the likelihoods of its predecessors in the DAG.<ref>{{citation|title=Probabilistic Boolean Networks: The Modeling and Control of Gene Regulatory Networks|publisher=Society for Industrial and Applied Mathematics|first1=Ilya|last1=Shmulevich|first2=Edward R.|last2=Dougherty|year=2010|isbn=978-0-89871-692-4|page=58|url=https://books.google.com/books?id=RfshqEgO7KgC&pg=PA58}}.</ref> In this context, the [[moral graph]] of a DAG is the undirected graph created by adding an (undirected) edge between all parents of the same vertex (sometimes called ''marrying''), and then replacing all directed edges by undirected edges.<ref>{{citation |last1= Cowell |first1= Robert G. |author2-link=Philip Dawid|last2=Dawid|first2=A. Philip|author3-link=Steffen Lauritzen|last3=Lauritzen|first3=Steffen L.|author4-link=David Spiegelhalter|last4=Spiegelhalter|first4=David J.|title= Probabilistic Networks and Expert Systems |publisher= Springer |year= 1999 |isbn= 978-0-387-98767-5 |chapter= 3.2.1 Moralization|pages= 31–33 }}.</ref> Another type of graph with a similar causal structure is an [[influence diagram]], the vertices of which represent either decisions to be made or unknown information, and the edges of which represent causal influences from one vertex to another.<ref>{{citation|title=The Technology Management Handbook|first=Richard C.|last=Dorf|publisher=CRC Press|year=1998|isbn=978-0-8493-8577-3|page=9{{hyphen}}7<!-- Do not conver this hyphen into a dash! It is a section-page number, not a range of page numbers. -->|url=https://books.google.com/books?id=C2u8I0DFo4IC&pg=SA9-PA7}}.</ref> In [[epidemiology]], for instance, these diagrams are often used to estimate the expected value of different choices for intervention.<ref>{{citation|title=Encyclopedia of Epidemiology, Volume 1|first=Sarah|last=Boslaugh|publisher=SAGE|year=2008|isbn=978-1-4129-2816-8|page=255|url=https://books.google.com/books?id=wObgnN3x14kC&pg=PA255}}.</ref><ref name="pearl:95">{{citation | last = Pearl | first = Judea | doi = 10.1093/biomet/82.4.669 | issue = 4 | journal = Biometrika | pages = 669–709 | title = Causal diagrams for empirical research | volume = 82 | year = 1995| url = https://escholarship.org/uc/item/6gv9n38c }}.</ref>
| |
− |
| |
− | Category:Directed graphs
| |
− |
| |
− | 类别: 有向图
| |
− |
| |
− |
| |
− |
| |
− | Category:Directed acyclic graphs
| |
− |
| |
− | 范畴: 有向无圈图
| |
− |
| |
− | The converse is also true. That is in any application represented by a directed acyclic graph there is a causal structure, either an explicit order or time in the example or an order which can be derived from graph structure. This follows because all directed acyclic graphs have a [[#Topological ordering|topological ordering]], i.e. there is at least one way to put the vertices in an order such that all edges point in the same direction along that order.
| |
− |
| |
− |
| |
− |
| |
− | de:Graph (Graphentheorie)#Teilgraphen.2C Wege und Zyklen
| |
− |
| |
− | de:Graph (Graphentheorie)#Teilgraphen.2C Wege und Zyklen
| |
− |
| |
− | <noinclude>
| |
− |
| |
− | <small>This page was moved from [[wikipedia:en:Directed acyclic graph]]. Its edit history can be viewed at [[有向无环图/edithistory]]</small></noinclude>
| |
− |
| |
− | [[Category:待整理页面]]
| |