Web图算法第15届国际研讨会无水印PDF

需积分: 10 86 浏览量更新于2024-07-18 收藏 31.4MB PDF 举报

"Algor for the Web Graph 15th International Workshop 无水印原版pdf" 是一本关于网络图算法和模型的会议论文集，由Anthony Bonato, Paweł Prałat 和 Andrei Raigorodskii 编辑，收录了在2018年5月17日至18日在俄罗斯莫斯科举行的第15届国际研讨会（WAW2018）上的研究成果。这本书属于《计算机科学讲义》系列，编号为10836，该系列始于1973年，由一系列知名学者担任过系列编辑。该书的内容涵盖了网络图的算法和模型，这些是理解互联网结构、行为和动态的关键工具。网络图在信息技术中起着核心作用，因为它们可以用来表示和分析复杂的网络系统，如社交网络、信息网络、基础设施网络等。研讨会的目标可能是促进理论研究与实际应用之间的交流，讨论最新的技术进展，并探索未来的研究方向。网络图的算法通常涉及节点（网页、用户、设备等）和边（连接、关系）的处理。这些算法可能包括但不限于： 1. **图遍历算法**：如深度优先搜索（DFS）和广度优先搜索（BFS），用于探索网络结构，找出路径或者检测连通性。 2. **最短路径算法**：Dijkstra算法和Floyd-Warshall算法等，用于在网络中寻找节点间最短的路径。 3. **社区检测算法**：如Modularity优化、Louvain方法或spectral clustering，用于识别网络中的紧密连接子群，这有助于理解网络的组织结构。 4. **排名算法**：如PageRank，这是Google搜索引擎中用于确定网页重要性的关键算法。 5. **图聚类系数和小世界现象**：分析网络中节点的局部聚集程度，以及网络是否表现出小世界特性，即大部分节点距离较近且存在少数高连接节点。 6. **复杂网络理论**：研究网络的幂律分布、小世界性和无标度特性，这些都是真实世界网络的典型特征。 7. **网络流算法**：用于解决在网络中如何有效地分配资源或信息流量的问题。 8. **随机游走和扩散模型**：模拟信息在网络中的传播过程，这对于广告推荐、疾病传播建模等有重要意义。 9. **网络稳定性和鲁棒性**：研究网络在遭受攻击或故障时的性能，以及如何设计更健壮的网络结构。 10. **图论在Web搜索和推荐系统中的应用**：利用图论工具优化搜索结果排序和个性化推荐。通过这样的研讨会和出版物，研究人员可以分享他们的新发现，推动网络图算法的创新，从而改进网络服务的性能，提高用户体验，并为解决现实世界问题提供新的思路和解决方案。

Finding Induced Subgraphs in Scale-Free Inhomogeneous Random Graphs 7

Furthermore,

P (w

∈ J

)=C((1 − ε)



μn)

1−τ

− C((1 + ε)



μn)

1−τ

≥ c

(

√

μn)

1−τ

(2.8)

for some constant c

> 0 because f

. Thus, each of the n vertices is in

set W



independently with probability at least c

(

√

μn)

1−τ

.Choose0<γ<c

Applying the multiplicative Chernoﬀ bound then shows that





| <γn

(3−τ)/2



≤ exp



−

− γ)

(3−τ)/2



, (2.9)

which proves the lemma together with (2.7) and the fact that

√

μn =

Ω(n

(3−τ)/2

)forτ ∈ (2, 3). 

We now use these lemmas to prove Theorem 1.

Proof of Theorem 1. We condition on the event that V



is of polynomial size

(Lemma 2) and that the weights are within the constructed lower and upper

bounds (Lemma 1), since both events occur with high probability. This bounds

the edge probability between any pair of nodes i and j in V



< min



(1 + ε)

√

μn(1 + ε)

√

μn

, 1



= f

(1 + ε)

, (2.10)

so that p

≤ p

= c

< 1 if we choose ε small enough. Similarly,

> min



(1 − ε)

√

μn



= Θ



log(n)



, (2.11)

by our choice of f

,sothatp

≥ p

−

= c

/ log(n). Let E := |E

| be the number

of edges in H. We upper bound the probability of not ﬁnding H in one of the

partitions of size k of V



as 1 −p

−

(1 −p

)

(

)

−E

. Since all partitions are disjoint

we can upper bound the probability of not ﬁnding H in any of the partitions as

P (H not in the partitions) ≤



1 − p

−

(1 − p

)

(

)

−E







. (2.12)

Using that E ≤ k





− E ≤ k

and that 1 − x ≤ e

−x

results in

P (H not in the partitions) ≤ exp



−p

−

(1 − p

)







. (2.13)

Since |V



| = Θ



3−τ



, |V



|/k≥dn

3−τ

/k for some constant d>0. We ﬁll in

the expressions for p

−

and p

, with c

> 0 a constant

P (H not in the partitions) ≤ exp



−

3−τ



log n





. (2.14)

8 E. Cardinaels et al.

Now apply that k ≤ log

(n). Then

P (H not in the partitions) ≤ exp



−

3−τ

log



log n



log



≤ exp



−dn

3−τ

−o(1)



(2.15)

Hence, the inner expression grows polynomially such that the probability of not

ﬁnding H in one of the partitions is negligibly small. The running time of the

partial search is given by







≤





≤ nk ≤ ne

, (2.16)

which concludes the proof for k ≤ log

1/3

(n). 

Proof of Corollary 1.Ifk>log

(n), we can determine whether H is an induced

subgraph by exhaustive search in time







≤

k(k − 1)

≤ kn

≤ ke

≤ ne

, (2.17)

since for all sets of k vertices the presence or absence of





edges needs to be

checked. For k ≤ log

(n), Theorem 1 shows that the induced subgraph isomor-

phism problem can be solved in time nk ≤ ne

. Thus, with high probability

the induced subgraph isomorphism problem can be solved in ne

time, which

proves that it is in typFPT. 

Proof of Theorem 2. The proof of Theorem 2 is very similar to the proof of

Theorem 1. The only way Algorithm 2 diﬀers from Algorithm 1 is in the selection

of the sets S

. As in the previous theorem, we condition on the event that



| = Θ(n

(3−τ)/2

) (Lemma 2) and that the weights of the vertices in G



are

bounded as in Lemma 1.

The graph G



constructed in Step 5 of Algorithm 2 then consists of

Θ(n

(3−τ)/2

) vertices. Furthermore, by the bound (2.11) on the connection prob-

abilities of all vertices in G



, the expected degree of a vertex i in G



satisﬁes

E [D

i,G



]=Ω(n

(3−τ)/2

/ log(n)). We can use similar arguments as in Lemma 1 to

show that D

i,G



= Ω(n

(3−τ)/2

/ log(n)) with high probability for all vertices in



. Since G



consists of Θ(n

(3−τ)/2

) vertices, D

i,G



= O(n

(3−τ)/2

) as well. This

means that for k<log

(n), Steps 8–11 are able to ﬁnd a connected subgraph

on k vertices with high probability.

We now compute the probability that S

is disjoint with the previous j − 1

constructed sets. The probability that the ﬁrst vertex does not overlap with the

previous sets is given by 1 − jk/|V



|, since that vertex is chosen uniformly at

random. The second vertex is chosen in a size-biased manner, since it is chosen

Finding Induced Subgraphs in Scale-Free Inhomogeneous Random Graphs 9

by following a random edge. The probability that vertex i is added can therefore

be bounded as

P (vertex i is added) =

i,G







s=1

s,G



≤

M log(n)



(2.18)

for some constant M>0 by the conditions on the degrees. Therefore, the prob-

ability that S

does not overlap with one of the previously chose jk vertices can

be bounded from below by

P (S

does not overlap with previous sets) ≥



1 −





1 −

Mkj log(n)





k−1

. (2.19)

Thus, the probability that all j sets do not overlap can be bounded as

P (S

∩ S

j−1

···∩S

= ∅) ≥



1 −

Mkj log(n)





, (2.20)

which tends to one when jk = o(n

(3−τ)/4

). Let s

dis

denote the number of disjoint

sets out of the s sets constructed in Algorithm 2. Then, when s = Ω(n

) for some

α>0, s

dis

for some β>0 with high probability, because k<log

1/3

(n).

The probability that H is present as an induced subgraph is bounded sim-

ilarly as in Theorem 1. We already know that k − 1 edges are present. For all

other E − (k − 1) edges of H, and all





− E edges that are not present in H,

we can again use (2.10) and (2.11) to bound on the probability of edges being

present or not being present between vertices in V



. Therefore, we can bound

the probability that H is not found similarly to (2.13)as

P (H not in the partitions) ≤ P (H not in the disjoint partitions)

≤ exp



−p

−

(1 − p

)

dis



Because s

dis

for some β>0, this term tends to zero exponentially. The

running time of the partial search can be bounded similarly to (2.16)as





≤ sk

= O(nk), (2.21)

whereweusedthats ≤ n/k. 

3 Experimental Results

Fig. 1 shows the fraction of times Algorithm 1 succeeds to ﬁnd a cycle of size

k in an inhomogeneous random graph on 10

vertices. Even though for large n

Algorithm 1 should ﬁnd an instance of a cycle of size k in step 7 of the algorithm

with high probability, we see that Algorithm 1 never succeeds in ﬁnding one. This

is because of the ﬁnite size eﬀects discussed before.

10 E. Cardinaels et al.

Fig. 1. The fraction of times step 7 in Algorithm 1 succeeds to ﬁnd a cycle of length k

on an inhomogeneous random graph with n =10

, averaged over 500 network samples

with f

=1/ log(n)andf

=0.9.

Figure 2a also plots the fraction of times Algorithm 2 succeeds to ﬁnd a cycle.

We set the parameter s = 10000 so that the algorithm fails if the algorithm does

not succeed to detect motif H after executing step 13 of Algorithm 2 10000

times. Because s gives the number of attempts to ﬁnd H, increasing s may

increase the success probability of Algorithm 2 at the cost of a higher running

time. However, in Fig. 2b we see that for small values of k, the mean number of

times Step 13 is executed when the algorithm succeeds is much lower than 10000,

so that increasing s in this experiment probably only has a small eﬀect on the

success probability. We see that Algorithm 2 outperforms Algorithm 1. Figure 2b

also shows that the number of attempts needed to detect a cycle of length k is

small for k ≤ 6. For larger values of k the number of attempts increases. This

can again be ascribed to the ﬁnite size eﬀects that cause the set V



to be small,

so that large motifs may not be present on vertices in set V



. We also plot the

success probability when using diﬀerent values of the functions f

and f

. When

only the lower bound f

on the vertex degrees is used, as in [11], the success

probability of the algorithm decreases. This is because the set V



now contains

many high degree vertices that are much more likely to form clique motifs than

cycles or other connected motifs on k vertices. This makes f

= ∞ a very eﬃcient

bound for detecting clique motifs [11]. For the cycle motif however, we see in

Fig. 2b that more checks are needed before a cycle is detected, and in some cases

the cycle is not detected at all.

Setting f

=0andf

= ∞ is also less eﬃcient, as Fig. 2a shows. In this

situation, the number of attempts needed to ﬁnd a cycle of length k is larger

than for Algorithm 2 for k ≤ 6.

3.1 Real Network Data

We now check Algorithm 2 on four real-world networks with power-law degrees:

a Wikipedia communication network [22], the Gowalla social network [22], the

Baidu online encyclopedia [23] and the Internet on the autonomous systems

level [22]. Table 1 presents several statistics of these scale-free data sets. Fig. 3

剩余193页未读，继续阅读

yinkaisheng-nj

粉丝: 762
资源: 6231

Web图算法第15届国际研讨会无水印PDF

Algor、Ansys在桥梁工程中的应用方法与实例.pdf

no matching key exchange algor

chg_alg_device_register

获取 jgrapht 所有节点的所有路径的算法

使用JGraphT进行拓扑排序

用java写一个Prim算法

最新资源