Ａ graph-theoretical approach for pattern discovery in epidemiological research
在病疫学中一种为了模式发现在的图理论方法。
图理论方法在疫学的模式发现中的应用。
主要内容：
1.构造二部图，表示风险因素和个体之间的联系。
2.找出二部图的模式，反应具有相同风险因素的一群体，并为每个模式量化其风险和
意义
3.把在第二步中找出的模式，按照偏序关系构成格。
4.进行分析。
1.构造二部图，表示风险因素和个体之间的联系。
个体对应着其相应的特征，把个体作为一个结点集(叫terminal nodes:t-node)，把这些个体对应的特征作为一个结点集(叫sources nodes:s-node)。如果s-node是t-node的一个特征，我们用一条边连接起，结果就成一个二部图。在这个图中，只有两类结点：t-node 和s-node；
并且同类型的结点之间是没有边相连接的。
几个相关的概念：
Clique：完全图(略)
Biclique：完全二部图 ：在第一结点集中的任一结点都与第二个结点集合的所有结点存在一条边连接。
最大完全二部图：在一个二部图中，如果没有一个比这更大的完全二部子图，那么这个完全二部子图即是最大完全二部子图。
在该文章中，找出所有的最大完全二部图是最感兴趣的。这是因为最大完全二部图表示存在一群个体共享相同的特征。同时，当特征的结点数增多时，共享相同特征的个体就会减少。由每一个特征集都能生成一个最大完全二部图。所有的特征集生成的最大完全二部图之间满足偏序关系，因此，由这些集合和它们之间的关系可以构成格。
几个因素：
为了量化模式的相关的自变量，文章给出了２×２的表如图所示：
A,b,c,d这四种变量代表的个体数，a,c是已经表现出了模式，而b,d只是有这个趋向。
Odds ratio：OR = (a.d)/(b.c)；当OR>1时，模式是一种病例模式；当OR<时模式有利保护。当OR=1时，模式和因变量没有联系。
阳性似然比：
注意到这个表中，当行和列固定后，唯一的自由度就是内部变量a.
当a=a0，且OR(a0)>1时，得到满足OR>=OR(a0)的表的概率是P-value；
2.找出模式。求最大完全二部图
构造一个二部图：Ｇ＝｛Ｓ，Ｔ，Ｅ｝，而现在的目标是找出最大完全二部图书
Ｂ＝｛Sb,Tb,Eb｝且Sb≤S；Tb≤T；Eb≤E。
文章里面给出了两类集合操作：C(s)={{s},T(s)} 其中s是s-二部图中的结点，T(s)是对应的t结点。现在有C(s1)={{s1},T(s1)}；C(s２)={{s２},T(s２)}，那么
Ｃ(S1US2)=[(S1US2),T(S1)∩T(S2)]
对于C(T)={S(T),T}相例似也有：C(T1UT2)=[S(T1)∩S(T2),(T1UT2)];
扩展集：X(S)={s|T(S)＜T(X(S))}；即：T(S)∩T(X(S))=T(S)。
通过扩展集找出最大二部子图。其流程图如下：
程序首先从构建二部图开始，另外建一张表映射表把原始的数据值转换为作为s-node的离散的，绝对的特征值t-node从原始记录标示中得到。
然后程序开始在case 图中搜索最大完全二部图。并得到相关的2×2表中变量的值。
每个找到的二部图都赋给相对应的品质因数，并检查用户定义的约束条件。品质因数包括p-value,OR，也可从2×2表中得到相关的约束条件。根据约束条件，输出或是进入扩展队列以循环扩充。在循环队列中，由品质因数确定候选二部图的优先级，品质因数好的被优先出队列进行扩展。
这个循环一直重复，直到候选队列为空为止，这是输出文件中包含了最大完全二部图的s-集合，t-集合，2×2表及相关的统计信息。
程序在搜索新的可接受的候选二部图时，候选队列顶部的候选二部图出列进行集合扩充。选中的二部图与其对应的邻接集进行集合操作产生新的集合，如果新二部图遇到约束条件时且在已经存在的二部图集中没有副本，则输出该二部图及相关信息，也添加到优先候选队列中参与循环。
3.构造格。
当前面的程序终止后，在输出文件中包含了所有的最大完全二部图以及相对应的信息。包括2×2表信息。把每个最大完全二部图做为一个用户个体，由这些个体之间和它们之间的偏序关系构建成一个格。
给两个最大完全二部图C1(S1,T1)和C2(S2,T2)，S1<S2当且仅当T1>T2,如果S1>S2当且仅当T1<T2，这种关系我们就可以构造一个模式格。这些最大完全二部图在模式格中就成了一个结点。模式格的图示如下：
4.进行结果分析（略）。