不确定图中最稠密子图的多项式时间算法
10 浏览量
更新于2024-08-28
收藏 132KB PDF 举报
"这篇研究论文探讨了在不确定图中寻找最稠密子图的问题。由于不确定性，传统的稠密子图定义不再适用于此类图。作者提出了不确定图的期望密度概念，并基于此定义了一个新问题：在给定的不确定图G=(V,E,P)和一个顶点集R⊆V中，找到具有最大期望密度的诱导子图G'=(V',E',P')，其中R⊆V'。论文展示了如何利用最大流技术在O(nmlog(n^2/m))的时间复杂度内找到最优解，其中n是顶点的数量，m是边的数量。此外，该模型比现有的不确定图模型更为通用，不假设边的存在性相互独立。论文被分类在离散数学的图论和数据库管理的数据挖掘应用领域。"
这篇论文主要涉及以下几个知识点：
1. **不确定图**：不确定图是一种包含不确定性信息的图结构，其中边的存在概率不是固定的，可能受多种因素影响，导致传统图论中的概念如度、连通性和密度等不再适用。
2. **期望密度**：论文引入了期望密度作为衡量不确定图稠密程度的新指标。期望密度考虑了每条边出现的概率，是计算所有可能子图密度的期望值。
3. **最稠密子图问题**：经典图论中的最稠密子图问题是寻找图中边数与顶点数比例最大的子图。在不确定图中，这个问题转化为寻找具有最大期望密度的子图。
4. **最大流算法**：论文提出使用最大流技术来解决这个优化问题。最大流算法常用于网络流问题，能找出在一个有向图中从源点到汇点的最大流量。在这里，它被用来确定能最大化期望密度的子图。
5. **时间复杂度**：论文中给出的算法在O(nmlog(n^2/m))的时间复杂度内运行，表明它在处理大规模数据时仍具有较好的效率。
6. **模型的通用性**：与已有的不确定图模型相比，该模型不假设边的存在性相互独立，因此更适应实际复杂情况，增加了模型的适用范围。
7. **领域分类**：论文属于计算机科学的离散数学分支，特别是图论算法，同时也关联到数据库管理领域的数据挖掘应用，表明这种方法可应用于数据挖掘和分析的场景。
这篇研究对于理解和处理含有不确定性的复杂网络数据，如社交网络、生物网络或传感器网络等，提供了新的理论工具和算法，有助于提高数据挖掘的准确性和效率。
Polynomial-Time Algorithm for Finding Densest
Subgraphs in Uncertain Graphs
Zhaonian Zou
School of Computer Science and Technology
Harbin Institute of Technology, China
znzou@hit.edu.cn
ABSTRACT
This paper studies the problem of finding the densest sub-
graph in an uncertain graph. Due to uncertainty in graphs,
the traditional definitions of dense subgraphs are not ap-
plicable to uncertain graphs. In this paper, we introduce
the expected density of an uncertain graph. Based on the
expected density, we formalize the problem that, given an
uncertain graph G = (V, E, P ) and a set of vertices R ⊆ V ,
finds an induced subgraph G
′
= (V
′
, E
′
, P
′
) of G of the max-
imum expected density such that R ⊆ V
′
. We show that the
optimal solution can be found in O(nm log(n
2
/m)) time us-
ing max imum flow techniques, where n = |V | and m = |E|.
Moreover, unlike the existing models of uncertain graphs,
the model used in this p aper is very general, which doesn’t
assume the existence of edges is mutually independent.
Categories and Subject Descriptors
G.2.2 [Discrete Mathematics]: Graph Theory — Graph
algorithms; H.2.8 [Database Management]: Database Ap-
plications — Data mining
General Terms
Measurement, algorithms, performance
Keywords
Uncertain graph, marginal constraint, expected density, para-
metric maximum flow
1. INTRODUCTION
Dense subgraph discovery is a fundamental problem in
the research on graph databases. In literature, a number of
algorithms have been proposed for finding dense subgraph-
s in a given graph, where a variety of definitions of dense
subgraphs have been used, e.g., cliques [23], quasi-cliques
[1], k-cores [10], k-truss [24], and so on. In this paper, we
consider the density measure that assesses th e ratio of the
Permission to make digital or hard copies of all or part of this work for per-
sonal or classroom use is granted without fee provided that copies are not
made or distributed for profit or commercial advantage and that copies bear
this notice and the full citation on the first page. Copyrights for components
of this work owned by others than the author(s) must be honored. Abstract-
ing with credit is permitted. To copy otherwise, or republish, to post on
servers or to redistribute to lists, requires prior specific permission and/or a
fee. Request permissions from Permissions@acm.org.
MLG’13, August 11, 2013, Chicago, Illinois, USA.
Copyright is held by the owner/author(s). Publication rights licensed to
ACM. ACM 978-1-4503-2322-2 ...$15.00..
v
4
v
5
v
1
v
3
v
2
0.7
0.8
0.8
0.2
0.91.0
0.1
0.7
Figure 1: Uncertain graph G.
number of edges to the number of vertices [12]. More precise-
ly, given a graph G = (V, E), the density of G is defined by
ρ(G) = |E|/|V |. This definition of density of graph G equiv-
alently measures the average d egree of G because 2|E|/|V |
is equal to the average degree of G. Based on this density
measure, many studies have been carried out on the prob-
lem of finding a subgraph or an induced subgraph of the
maximum density in a given graph [4, 8, 9, 12].
Recently, uncertainty has been recognized to be intrin-
sic in large graph databases due to errors of measurements,
delayed updates of data, and data integration. Managing
and mining uncertain graph data have attracted a lot of re-
search attentions [14, 15, 16, 17, 18, 20, 21, 25, 26, 27]. In
our prior work [27], we define an uncertain graph by a triple
G = (V, E, P ), where each edge e ∈ E has a probability
of P (e) to exist in practice. Due to uncertainty, the tradi-
tional defi nition of density ρ(G) of a graph G doesn’t make
sense on an uncertain graph. Consider the uncertain graph
G = (V, E, P ) in Figure 1, where the real number on each
edge e is P (e). If we t hink of G as an exact graph, the densi-
ty of G is 8/5. However, since edges (v
2
, v
4
) and (v
3
, v
5
) exist
with very low probability, the density of G should actually
be much lower than 8/5, and be close to 6/5.
In t his paper, we first formalize the problem of finding the
densest subgraph in an uncertain graph. A ccording to our
uncertain graph model, an uncertain graph G = (V, E, P )
exists as an exact graph G
′
= (V, E
′
) in practice, where
each edge e ∈ E exists in E
′
with probability P (e). More
formally, we say that G implicates G. Let Ω(G) be the set
of exact graphs implicated by G. The uncertain graph G es-
sentially represents a probability mass function p over Ω(G),
where p(G) is equal to the probability of G implicating G
for all G ∈ Ω(G). For each exact graph G = (V, E) ∈ Ω(G),
the density of G is ρ(G) = |E|/|V |. Therefore, we evaluate
the density of G by the expected value of density of an exact
graph G chosen at random from Ω(G) according to proba-
bility m ass function p. Namely, this measure is called the
下载后可阅读完整内容，剩余6页未读，立即下载
2012-11-15 上传
2009-12-20 上传
2020-02-08 上传
2021-03-26 上传
2021-04-22 上传
2021-02-11 上传
2021-04-13 上传
2021-04-30 上传
2021-04-05 上传
weixin_38680506
- 粉丝: 4
- 资源: 927
我的内容管理
展开
最新资源
- 黑板风格计算机毕业答辩PPT模板下载
- CodeSandbox实现ListView快速创建指南
- Node.js脚本实现WXR文件到Postgres数据库帖子导入
- 清新简约创意三角毕业论文答辩PPT模板
- DISCORD-JS-CRUD：提升 Discord 机器人开发体验
- Node.js v4.3.2版本Linux ARM64平台运行时环境发布
- SQLight：C++11编写的轻量级MySQL客户端
- 计算机专业毕业论文答辩PPT模板
- Wireshark网络抓包工具的使用与数据包解析
- Wild Match Map: JavaScript中实现通配符映射与事件绑定
- 毕业答辩利器：蝶恋花毕业设计PPT模板
- Node.js深度解析：高性能Web服务器与实时应用构建
- 掌握深度图技术：游戏开发中的绚丽应用案例
- Dart语言的HTTP扩展包功能详解
- MoonMaker: 投资组合加固神器，助力$GME投资者登月
- 计算机毕业设计答辩PPT模板下载
