グラフの密度

k-coreが気になるのでDensity-friendly graph decomposition ( https://users.ics.aalto.fi/gionis/friendly.pdf )を読む。Google翻訳まんまだけど


Abstract

Decomposing a graph into a hierarchical structure via k-core analysis is a standard operation in any modern graph mining toolkit.
k-core decomposition is a simple and efficient method that allows to analyze a graph beyond its mere degree distribution.
More specifically, it is used to identify areas in the graph of increasing centrality and connectedness, and it allows to reveal the structural organization of the graph.

最新のグラフマイニングツールキットでは、kコア分析を介してグラフを階層構造に分解することが標準的な操作です。
kコア分解は、単なる次数分布を超えてグラフを分析することを可能にする、単純かつ効率的な方法である。
より具体的には、それは、増加する中心性および連結性のグラフ内の領域を識別するために使用され、グラフの構造的構成を明らかにすることを可能にする。

Despite the fact that k-core analysis relies on vertex degrees, k-cores do not satisfy a certain, rather natural, density property.
Simply put, the most central k-core is not necessarily the densest subgraph.
This inconsistency between k-cores and graph density provides the basis of our study.

kコア分析が頂点の度合いに依存するという事実にもかかわらず、kコアはある種の、むしろ自然な密度特性を満たさない。
簡単に言えば、最も中央のkコアが、必ずしも最も密度の高いサブグラフであるとは限りません。

kコアとグラフ密度との間のこの不一致が我々の研究の基礎を提供する。

We start by defining what it means for a subgraph to be locally-dense,
and we show that our definition entails a nested chain decomposition of the graph, similar to the one given by k-cores,
but in this case the components are arranged in order of increasing density.

サブグラフが局所的に密集することを意味するものを定義することから始め、私たちの定義には、kコアによって与えられたものと同様に、グラフのネストされたチェーン分解が必要であることを示しています。この場合、構成要素は、密度が増加する順に配置される。

We show that such a locally-dense decomposition for a graph G = (V, E) can be computed in polynomial time.
The running time of the exact decomposition algorithm is O(|V|^2|E|) but is significantly faster in practice.
In addition, we develop a lineartime algorithm that provides a factor-2 approximation to the optimal locally-dense decomposition.

グラフG =(V、E)に対するこのような局所的に密な分解は、多項式時間で計算できることを示す。正確な分解アルゴリズムの実行時間はO(| V | ^ 2 | E |)であるが、実際にはかなり速い。さらに、局所的に最適な最適分解に第2因子近似を提供する線形アルゴリズムを開発する。

Furthermore, we show that the k-core decomposition is also a factor-2 approximation,however, as demonstrated by our experimental evaluation,
in practice k-cores have different structure than locally-dense subgraphs, and as predicted by the theory, k-cores are not always well-aligned with graph density.

さらに、kコア分解も第2因子近似であることを示す。
しかし、我々の実験評価によって示されるように、実際には、kコアは局所的に密なサブグラフとは構造が異なり、理論によって予測されるように、kコアは必ずしもグラフ密度とよく一致するとは限らない。

INTRODUCTION

Finding dense subgraphs and communities is one of the most well-studied problems in graph mining.
Techniques for identifying dense subgraphs are used in a large number of application domains, from biology, to web mining, to analysis of social and information networks.
Among the many concepts that have been proposed for discovering dense subgraphs, k-cores are particularly attractive for the simplicity of their definition and the fact that they can be identified in linear time.

高密度サブグラフとコミュニティを見つけることは、グラフマイニングで最もよく研​​究されている問題の1つです。
高密度サブグラフを識別する技術は、生物学からウェブマイニング、社会および情報ネットワークの分析まで、多数の応用分野で使用されている。
高密度サブグラフを発見するために提案された多くの概念の中で、kコアは、その定義の単純さと線形時間で識別できるという事実のために特に魅力的である。

The k-core of a graph is defined as a maximal subgraph in which every vertex is connected to at least k other vertices within that subgraph.
A k-core decomposition of a graph consists of finding the set of all k-cores.
A nice property is that the set of all k-cores forms a nested sequence of subgraphs, one included in the next.
This makes the k-core decomposition of a graph a useful tool in analyzing a graph by identifying areas of increasing centrality and connectedness, and revealing the structural organization of the graph.
As a result, k-core decomposition has been applied to a number of different applications, such as modeling of random graphs [8], analysis of the internet topology [12], social-network analysis [23], bioinformatics [6], analysis of connection matrices of the human brain [16], graph visualization [3], as well as influence analysis [19, 28] and team formation [9].

グラフのkコアは、すべての頂点がそのサブグラフ内の少なくともk個の他の頂点に接続されている最大部分グラフとして定義されます。
グラフのkコア分解は、すべてのkコアの集合を求めることからなる。
素敵な特性は、すべてのkコアのセットがサブグラフのネストされたシーケンスを形成することです。
これにより、グラフのkコア分解は、増加する中心性および連結性の領域を特定し、グラフの構造的構成を明らかにすることによってグラフを分析するのに有用なツールになります。
その結果、k-core分解は、ランダムグラフのモデリング[8]、インターネットトポロジーの分析[12]、ソーシャルネットワーク分析[23]、バイオインフォマティクス[6]などの多くの異なるアプリケーションに適用されてきた。人間の脳の接続行列の分析[16]、グラフの視覚化[3]、影響分析[19、28]、チーム形成[9]。

The fact that the k-core decomposition of a graph gives a chain of subgraphs where vertex degrees are higher in the inner cores, suggests that we should expect that the inner cores are, in certain sense, more dense or more connected than the outer cores. As we will show shortly, this statement is not true.
Furthermore, in this paper we show how to obtain a graph decomposition for which the statement is true, namely, the inner subgraphs of the decomposition are denser than the outer ones.

グラフのkコア分解が、内側コアの頂点の度数が高いサブグラフの連鎖を与えるという事実は、内側コアが特定の意味では、外側コアよりも密度が高く、接続されていることを期待するべきであることを示唆している。まもなく表示されるように、この記述は真実ではありません。
さらに、この論文では、文が真である、すなわち分解の内側の部分グラフが外側のグラフよりも密度が高いグラフ分解を得る方法を示す。

To quantify density, we adopt a classic notion used in the densest-subgraph problem [13, 15], where density is defined as the ratio between the edges and the vertices of a subgraph.
This density definition can be also viewed as the average degree divided by 2.
Our motivating observation is that k-cores are not ordered according to this density definition.
The next example demonstrates that the most inner core is not necessarily the densest subgraph, and in fact, we can increase the density by either adding or removing vertices.

密度を定量化するために、densest-subgraph問題[13、15]で使用される古典的な概念を採用します。密度は、サブグラフのエッジと頂点の比として定義されます。
この密度の定義は、平均次数を2で割ったものとして見ることもできます。
我々の動機づけは、この密度の定義に従ってkコアが順序付けされていないことである。
次の例は、最も内側のコアが必ずしも最も細いサブグラフではないことを示しています。実際、頂点を追加または削除することで密度を上げることができます。

Example 1. Consider the graph G1 shown in Figure 1, consisting of 6 vertices and 9 edges.
The density of the whole graph is 9/6 = 1.5.
The graph has three k-cores: a 3-core marked as C1, a 2-core marked as C2, and a 1-core, corresponding the the whole graph and marked as C3.
The core C1 has density 6/4 = 1.5 (it contains 6 edges and 4 vertices), while the core C2 has density 8/5 = 1.6 (it contains 8 edges and 5 vertices).
In other words, C1 has lower density than C2, despite being an inner core.

例1 6つの頂点と9つの辺からなる図1のグラフG1を考えてみましょう。
グラフ全体の密度は9/6 = 1.5です。
このグラフには、3つのkコアがあります。C1としてマークされた3コア、C2としてマークされた2コア、および1コアであり、グラフ全体に対応し、C3としてマークされています。
コアC1は密度6/4 = 1.5(6つのエッジと4つの頂点を含む)を有し、コアC2は密度8/5 = 1.6(8つのエッジと5つの頂点を含む)を有する。
言い換えれば、C1は内部コアであるにもかかわらずC2よりも密度が低い。

Let us now consider G2 shown in Figure 1.
This graph has a single core, namely a 2-core, containing the whole graph.
The density of this core is equal to 11/8 = 1.375. However, a subgraph B1 contains 7 edges and 5 vertices, giving us density 7/5 = 1.4, which is higher than the density of the only core.
This example motivates us to define an alternative, more density-friendly, graph decomposition, which we call locallydense decomposition.

図1に示すG2について考えてみましょう。
このグラフには、単一のコア、つまり2コアがあり、グラフ全体が含まれています。
このコアの密度は11/8 = 1.375に等しい。しかし、サブグラフB1は7つのエッジと5つの頂点を含み、密度7/5 = 1.4を与え、これは唯一のコアの密度よりも高い。
この例では、より密度の高い代替のグラフ分解を定義するよう動機づけています。グラフ分解は、局所的分解と呼ばれます。

We are interested in a decomposition such that
(i) the density of the inner subgraphs is higher than the density of the outer subgraphs,
(ii) the most inner subgraph corresponds to the densest subgraph, and
(iii) we can compute or approximate the decomposition efficiently.

We achieve our goals by first defining a locally-dense subgraph, essentially a subgraph whose density cannot be improved by adding and deleting vertices.
We show that these subgraphs are arranged into a hierarchy such that the density decreases as we go towards outer subgraphs and that the most inner subgraph is in fact the densest subgraph.
We provide two efficient algorithms to discover this hierarchy.

私たちは分解に興味があります。
(i)内側サブグラフの密度が外側サブグラフの密度よりも高く、
(ii)最も内側のサブグラフは最も細いサブグラフに対応し、
(iii)分解を効率的に計算または近似することができる。

局所的に密集した部分グラフを定義することで目標を達成します。本質的には、頂点を追加したり削除して密度を上げることはできません。
これらの部分グラフは、外側の部分グラフに行くにつれて密度が減少し、最も内側の部分グラフが実際には最も細い部分グラフであるような階層に配置されることを示す。
この階層を発見するための2つの効率的なアルゴリズムを提供します。

The first algorithm extends the exact algorithm for discovering the densest subgraph given by Goldberg [15].
This algorithm is based on solving a minimum cut problem on a certain graph that depends on a parameter α.
Goldberg showed that for a certain value α (which can be found by binary search), the minimum cut recovers the densest subgraph.
One of our contributions is to shed more light into Goldberg’s algorithm and show that the same construction allows to discover all locally-dense subgraphs by varying α.

最初のアルゴリズムは、Goldberg [15]によって与えられた最も細いサブグラフを発見するための正確なアルゴリズムを拡張する。
このアルゴリズムは、パラメータαに依存する特定のグラフ上の最小カット問題を解くことに基づいている。
Goldbergは、ある値α(バイナリサーチで見つかる)に対して、最小カットは最も細いサブグラフを回復することを示した。
我々の貢献の1つは、ゴールドバーグのアルゴリズムをより明らかにし、同様の構成がαを変化させることによってすべての局所的に密な部分グラフを発見することを可能にすることである。

Our second algorithm extends the linear-time algorithm by Charikar for approximating dense subgraphs [13].
This algorithm first orders vertices by deleting iteratively a vertex with the smallest degree, and then selects the densest subgraph respecting the order.
We extend this idea by using the same order, and finding first the densest subgraph respecting the order, and then iteratively finding the second densest subgraph containing the first subgraph, and so on.
We show that this algorithm can be executed in linear time and it achieves a factor-2 approximation guarantee.

我々の第2のアルゴリズムは、密集した部分グラフを近似するためのCharikarによる線形時間アルゴリズムを拡張する[13]。
このアルゴリズムは、最初に最小次数の頂点を繰り返し削除することによって頂点を順序付けし、次にその順序を考慮して最も細いサブグラフを選択する。
この考え方は、同じ順序を使用して、順序を考慮した最初の最も細いサブグラフを見つけ、最初のサブグラフを含む2番目に細かいサブグラフを繰り返し検索するなどして拡張します。
このアルゴリズムは線形時間で実行可能であり、第2因子近似保証を達成することを示す。

Charikar’s algorithm and the algorithm for discovering a k-core decomposition are very similar:
they both order vertices by deleting vertices with the smallest degree.
We show that this connection is profoundly deep and we demonstrate that a k-core decomposition provides a factor-2 approximation for locally-dense decomposition.


Charikarのアルゴリズムとkコア分解を発見するためのアルゴリズムは非常に似ています。それらは両方とも、最小次数の頂点を削除することによって頂点を順序付けます。
この接続が深く深いことを示し、kコア分解が局所的に密な分解のための第2因子近似を提供することを示す。

On the other hand, our experimental evaluation shows that in practice k-cores have different structure than locally-dense subgraphs, and as predicted by the theory, k-cores are not always well-aligned with graph density.
The remainder of paper is organized as follows.
We give preliminary notation in Section 2.
We introduce the locallydense subgraphs in Section 3,
present algorithms for discovering the subgraphs in Section 4,
and describe the connection to k-core decomposition in Section 5.
We present the related work in Section 6 and present the experiments in Section 7.
Finally, we conclude the paper with discussion in Section 8.


一方、実際にはkコアは局所的に密なサブグラフとは構造が異なり、kコアは必ずしもグラフ密度とよく一致するとは限らないことが理論的に予測されている。
論文の残りは次のように編成されている。
第2節では予備的表記法を用いる。
3章で局所的な部分グラフを紹介し、
セクション4の部分グラフを発見するための現在のアルゴリズム
セクション5のkコア分解への接続について説明します。
6章で関連する作業を提示し、7章で実験を提示する。
最後に、8章で議論した論文を締めくくる。

Git LFSは別にリポジトリサーバー側で対応が必要なわけではなくて、LFSサーバーが必要なだけ

GitHubやbitbucketのLFS対応もなんかストレージの料金がすごい高いなぁとおもっていて、リポジトリをホストするサーバーで対応が必要とおもっていたのですが、調べてみるとどうやら違うようでした。

ydkk.hateblo.jp

LFSサーバーをAWS Lambdaに構築して、S3をストレージにする実装

仕組みとしてはLFS サーバーとして、ラージファイルを保存した/保存できるURLを提供する。
git lfsのコマンドがpull / pushの時にLFSサーバーと連携して、オブジェクト(LFS track対象のファイル)をLFSサーバーが返すURLにGET / PUTするという仕組みでした。

他にもLFSサーバーと連携しないstandalone transfer agentの仕組みなどがあるようです。
https://github.com/git-lfs/git-lfs/blob/master/docs/custom-transfers.md


LFSサーバーなしでS3をストレージにする実装としては、下記のようなものがありました。
github.com


なんか不思議な感じです。

GitHubやbitbucketもAPIトークンを登録するとか、AzureのBlog StorageのSASトークンを登録することで、クラウド上で提供されているストレージをLFSのバックエンドとして使わせるとかできるはずなのになんでしないんだろうという感じです。
みんながほしいソリューションはそっちじゃなかろうかとおもうのです。

TCP over websocket

仕事の関係でKeycloakとその下回りであるJBoss/WildFlyを調べていて面白い記事を見つけました。

EJB呼び出しなどは以前はRMI/IIOPのようなTCP/IP上のプロトコルを使っていたが、いまはWebSocket上で行っている(TCP over WebSocket)という記事です。これはWildFly8の頃で、現在の12ではまた別のプロトコルに代わっています。

これと並行してKeycloakでWebSocketを保護できるという話を見つけました。

OAuth2のアクセストークンの期限切れをwebsocketに反映させるとかはできないけど、認証だけならアダプタ入れるだけでできるよという話です。
プロトコル的にはまずHTTP 1.1 GETと一緒にUpgrade要求をするので、その間にOAuth2の認可フローを差し込めるというのがプロトコル上の理解です。

上記のような話題からウェブサーバーとしてOpenID connect / OAuth2などと連携するVPN/トンネリング製品ができるなとおもっていたのですが、https://kaazing.com/ というのがまさにそういう製品のようです。

chisel(https://github.com/jpillora/chisel)というgoで作られた、やはり同様のOSSがあったのですが、保護までしてくれないようだったのですが、chiselもApacheのmod_wstunnel / mod_auth_openidcとかと組み合わせればいけそうな気がします。

すこしこのあたりに興味がわいてきました。

俺のFPTの理解

FPTにおいては幅とパラメータが存在する。

たとえば幅をk-coreとすることができるというのが、最大クリーク問題つづき - 高温処理済みコースケの話。
k-クリーク判定では幅hに対しての組み合わせになるので二項定理から {}_{h}\mathrm{C}_{k} = {}_{h}\mathrm{C}_{h-k}なので、 min(k,h-k)を用いて h^{min(k,h-k)}のオーダーで上限を決めることができる。

今回、最大クリーク問題の幅をk-coreとしたが、その幅は彩色数の近似にもできる。
k-coreの順序で貪欲彩色することにより、k-core + 1以下の彩色結果が得られるので、それを幅にしてもよい。
その場合でも上限は幅をもとに計算することができる。

W[1]-completeとはおそらくこの幅hとパラメータkの2変数により f(h,k)p(n)となるものだと考える。幅はアルゴリズム上設定されたもので、kは判定問題に与えられるパラメータ。これが指数関数しかないのか、多項式のものもあるのかはまだわからない。探索木を多項式時間で検索できればよい。結構制限はあるなかでの探索なのでもしかすると多項式時間のアルゴリズムがあるかもしれない。

指数時間アルゴリズム入門だと100万頂点からサイズ30以下の頂点被覆を求めることが可能ってなってたけど、補グラフの最大クリークのサイズをnから引いたものが頂点被覆なわけだから、幅hに対してk,h-kが小さければ、もっと全然できるはず。

Clique problem - Wikipedia 英語のWikiPediaの記事でDegeneracyをつかって最大クリーク問題ができるのが書いてあるな。

指数時間アルゴリズム入門だとkに対してと書いてあるので、2変数はちがうんだろうなとおもう。

最大クリーク問題つづき

グラフのDegeneracyをkとすると前処理後、おおまか 2^{k}n  で最大クリークが求まるな。

Degeneracyのページにしたがって、最大出次数を最小化するように、無向グラフ G(V,E)を順序付け、辺を向き付けし、有向グラフに変換する。これは多項式時間でできる。

最大出次数を \Delta_+とする。

頂点が順序付けされたので、 vを始点とするクリーク集合というのが扱えるようになった。
頂点 vとその出力辺からなる隣接集合から誘導される部分グラフH_v vを始点とするクリーク集合がすべて含まれる。

このH_vvを除く頂点の組み合わせをすべて試せば、vを含むクリークの最大サイズがわかる。
 \Delta_+は最小化されていて、n頂点すべてについて行うので、大まか 2^{\Delta_+} n でもとまる。

もうすこしアルゴリズムとして分解することにする。

頂点の冪集合P(V)のうち、特にサイズがkのものを P_k(V) \subset P(V)と書く。
fをサイズkの頂点集合がクリークであればkを、そうでなければ-1を返すものとする。これは誘導部分グラフを作成し、頂点数と辺数から決めることができ多項式時間である。
 \displaystyle f: P_k(V) \rightarrow \{k,-1\}

 T_vをある頂点vの出力辺から作成される隣接集合とすると、最大クリークをもとめる \omega(G)は下記のような形になる。

 \displaystyle \omega(G) = \max_{v \in V} \max_{k=0,1,\cdots} \max\{\max \{ f(\{v\} \cup T_v \setminus X),\> f(\{v\} \cup X)\} |  X \in P_{k}(T_v) \}

上記の式は下限、上限から挟み撃ちにしている。

 f(\{v\} \cup T \setminus X) > 0となるときは、明らかに vを始点とする最大クリークであり、次の頂点に移ればよい。最も内側のmax式が-1の時は、下でクリークが見つからないわけなので、そこまでに見つかった最大クリークサイズを返して、やはり次の頂点に移る。*1

判定式のほうはkを求めるクリークサイズとすると d_+(v) - k,kの小さいほうを使用する。これを k'とするとおおまか計算量は {}_{\Delta_+}\mathrm{C}_{k'} nになる。
もちろん k > \Delta_+であれば解はない。

 \displaystyle 
\begin{eqnarray}
\omega(G,k) & = & \max_{v \in V} \max_{X \in P_{k}(T_v)} f(\{v\} \cup X) & \hspace{1cm} & (d_+(v) - t \ge k) \\
                 & = & \max_{v \in V} \max_{X \in P_{k'}(T_v)} f(\{v\} \cup T_v \setminus X) & \hspace{1cm} & (d_+(v) - t \lt k)
\end{eqnarray}

最悪のケースは \frac{\Delta_+}{2} = \omega(G)のときで、例えば K_2が50個あるようなグラフの補グラフだと思う。サイズ50のクリークが2^{50}個あって、98正則グラフなので \Delta_+ = 98。正確に半分ではないけどイメージは伝わると思う。これは補グラフが連結ではないことが頂点数、辺数からわかるので状況に合わせて必要な処理を組み込むことで平均的な時間はもっと高速化できる。
おそらくこのアルゴリズムはZPPである。
まとめ

自分の理解ではおそらくNP困難問題である最大クリーク問題がPであり、NP完全問題であるk-クリーク問題がFPTになった。
もし違う観点があるとすれば、最大クリーク問題が f(\Delta_+)p(n)のFPTで、k-クリーク問題が f(\Delta_+,k)p(n)のFPTという感じ。

最大次数やk-core数なんてデータの入力長に依存しないのでPだと思っている。が、アルゴリズムで設定された幅とみれば、それは指数時間なのかもしれない。

その他
従来のFTPの議論では最大クリークや最大独立集合にFPTがないといわれていたが、次数から引くというとのが盲点だったのかなと思った。
ただ無向グラフでvを含むクリークの最大を全部数えるでも、おそらくここに行きつくので最大次数は最小化できないという意味で有向グラフに変換するというが転換だったなのかなと思う。

(以下、全部 たぶん)

P≠NP予想は否定したとおもう。
#PもPである。P=NPであったので多項式階層はすべて潰れた

そしてP=ZPPである。P=ZPPからZPP≠EXPTIMEになる。
P=NPなのでETH, SETHも否定した。


参考 : NP困難 - Wikipedia
参考: #P - Wikipedia
参考: P≠NP予想 - Wikipedia
参考: 多項式階層 - Wikipedia
参考 : Fixed Parameter Algorithms Open lectures for PhD students in computer science
参考: ZPP - Wikipedia

*1:ただ、なんとなく中央まで行くのではなくて、3分の1進めたところで下限のほうのクリークの集合から2つ選んで最大クリークを探すほうが良い気がする。

K4の対辺をつなぐ話(2)

前、こういうのを考えて、最大クリーク数もなんとなく半分になりそうって書いたんだけど、
kousuke.hatenablog.com

それって式にするとこういうことになるのかな?
 \chi(f(K_n)) = \lfloor \frac{\chi(K_n) }{2} \rfloor

fは G(V,E)の辺を頂点にして、 e_i \cup e_j K_4の時に辺とするような変換。
完全グラフについては証明できそうだけどな。


一般のグラフでも下記の形で成り立つとすれば
 \chi(f(G)) = \lfloor \frac{\chi(G) }{2} \rfloor

これを繰り返して、最大クリーク数が 2^n \le \chi(G) \lt 2^{n+1}の範囲で求められそうとおもったよ。