Differentially Private Analysis of Graphs
Differentially Private Analysis of Graphs
复制标题
图的差分隐私分析
DOI：
10.1007/978-1-4939-2864-4
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Smith, Adam
中科院分区：
文献类型：
--
作者：
Raskhodnikova, Sofya;Smith, Adam
这个问题是一个关于叶子标记的树的模式匹配问题。每个输入树被认为是一个分支模式，诱导特定的叶子组。给定一组具有相同叶集的输入树，目标是在输入树的分支模式上找到一个最大的叶子集。最大兼容树是具有这样一个叶子集的树，并且具有输入树与这些叶子相关联的分支模式。最大相容树问题（Maximum Compatible Tree problem, mct）就是找到这样一棵树，或者等价地，找到它的叶集。这个问题的主要动机是在系统发育中，测量进化树之间的相似性，或者表示一组树的共识。这个问题在[9]和[10]中被引入，在MRST的缩写下。以前的相关工作涉及著名的最大一致子树问题（mast）。求解mast就是找到所有输入树都完全一致的叶子的最大子集。mast和mct的区别在于，mast寻找的树的分支信息与每个输入树中的子树的分支信息同构，而mct寻找的树包含每个输入树的子树的分支信息（即组）。这种差异使得为mct获得的树具有更多的信息，因为它可以包括一个输入树中存在的分支信息，而不是其他输入树中的分支信息，只要这些信息与它们兼容。当所有的输入树都是二叉树时，这两个问题是等价的。Ganapathy和Warnow[5]是第一个给出一般形式的mct求解算法的人。他们的算法依赖于一种简单的动态规划方法，类似于在mast[12]上的工作，并且在输入树的数量和输入树中节点的最大程度上具有运行时间指数。后来，[2]提出了一种只使用一个参数的固定参数算法。近似结果也得到了[1,6]，结果是低成本的多项式时间算法在一个恒定的阈值内近似mct的补。这里考虑的树是进化树（系统发生）。这样的树T的叶集L (T)与标签集成双射，并且是有根的，在这种情况下，所有内部节点每个至少有两个子节点，或者是无根的，在这种情况下，内部节点的度数至少为3。给定一个标签集合L和一棵树T， T对L的限制，记作T| L，是这样得到的树：取L∩L (T)中连接带有标签的叶子的T的最小诱导子图，然后去掉任意二阶（非根）节点，使树同态不可约。两棵树T， T ‘是同构的，记作T= T ’，当且仅当存在一个图同构T∈→T '保留叶标记（且当两棵树都是根）。树T细化树T ‘，记为T⊵T ’，只要T可以通过折叠其内部的一些边（折叠一条边意味着删除它并合并它的端点）转换为T '。图1给出了树之间这些关系的示例。注意，一棵树T正确地精炼了另一棵树T '，与整个树一致
This problem is a pattern matching problem on leaf-labeled trees. Each input tree is considered as a branching pattern inducing specific groups of leaves. Given a set of input trees with identical leaf sets, the goal is to find a largest subset of leaves on the branching pattern of which the input trees do not disagree. A maximum compatible tree is a tree with such a leaf-set and with the branching patterns associated to these leaves by the input trees. The Maximum Compatible Tree problem (mct) is to find such a tree or, equivalently, its leaf set. The main motivation for this problem is in phylogenetics, to measure the similarity between evolutionary trees, or to represent a consensus of a set of trees. The problem was introduced in [9] and [10, under the MRST acronym]. Previous related works concern the well-known Maximum Agreement Subtree problem (mast). Solving mast is finding a largest subset of leaves on which all input trees exactly agree. The difference between mast and mct, is that mast seeks a tree whose branching information is isomorphic to that of a subtree in each of the input trees, while mct seeks a tree that contains the branching information (ie groups) of a subtree of each input tree. This difference allows the tree obtained for mct to be more informative, as it can include branching information present in one input tree but not in the others, as long as this information is compatible with them. Both problems are equivalent when all input trees are binary. Ganapathy and Warnow [5] were the first to give an algorithm to solve mct in its general form. Their algorithm relies on a simple dynamic programming approach similar to a work on mast [12] and has a running time exponential in the number of input trees and in the maximum degree of a node in the input trees. Later,[2] proposed a fixed-parameter algorithm using one parameter only. Approximation results have also been obtained [1, 6], the result being low-cost polynomial-time algorithms that approximate the complement of mct within a constant threshold.Notations Trees considered here are evolutionary trees (phylogenies). Such a tree T has its leaf set L (T) in bijection with a label set and is either rooted, in which case all internal nodes have at least two children each, or unrooted, in which case internal nodes have a degree of at least three. Given a set L of labels and a tree T, the restriction of T to L, denoted T| L, is the tree obtained in the following way: take the smallest induced subgraph of T connecting leaves with labels in L∩ L (T), then remove any degree two (non-root) node to make the tree homeomorphically irreducible. Two trees T, T′ are isomorphic, denoted T= T′, if and only if there is a graph isomorphism T↦→ T′ preserving leaf labels (and the root if both trees are rooted). A tree T refines a tree T′, denoted T⊵ T′, whenever T can be transformed into T′ by collapsing some of its internal edges (collapsing an edge means removing it and merging its extremities). See Figure 1 for examples of these relations between trees. Note that a tree T properly refining another tree T′, agrees with the entire