ラベル グラフ理論 の投稿を表示しています。 すべての投稿を表示
ラベル グラフ理論 の投稿を表示しています。 すべての投稿を表示

2014年5月11日日曜日

[Gremlin] OrientDBをGremlinから使うとaddEdgeしても反応がない!?

OrientDBは、オープンソースのグラフDB(かつドキュメントDB)である。
グラフDBといえばNeo4jなんだけど、やんごとなき事情によりOrientDBを使ってみることにしたらタイトルの件でハマった。

簡単な用語説明

グラフとは?:

Excelのアレではなく、点と点を線が結ぶアレ。

グラフDBとは?:

いわゆるDBであるところのRDB(MySQLとか)は、データを表形式として扱うようデザインされている。
グラフDBは、データを点と点と線の繋がりとして扱うようにデザインされている。
データの一覧を上から下まで流し見るようなクエリは苦手だが、あなたの買った本を買ったユーザが買った本の・・・みたいに、繋がりをずるずると解決していくようなクエリが得意。

Gremlinとは?:

グラフ処理関連製品を黙々と開発し続ける謎の開発者集団TinkerPopがリリースしたグラフクエリ言語(正確には、スクリプト言語的にグラフクエリを行うためのフレームワークって感じ)。
夜に食べ物を与えてはならず、水を掛けてはいけないアレが名前とキャラクターのモチーフのようだ。

事象

VertexとEdgeをいくらか作成するようなGremlinスクリプトを流すと、Vertexはきちんと増えているんだけど、Edgeの数(g.E.count()の結果)が0と出る。またg.Eの結果がなにも帰ってこない。
公式サイトから落とせるバイナリのバージョンがまだrcなのでバグなのか!?とか、
もしやVertexとEdgeでパーミッションが別で、Edgeの書き込み権限だけないのか!?とか、
いろいろ想像と調査をめぐらした結果、ずばりの事象についてGitHubのWikiに書いてあることがわかった。

要約すると、OrientDBで、設定がデフォルトの状態で、propertyを含まないEdgeを追加した場合、
直接参照できない"LightWeightEdge"、つまり「見えないEdge」が作成されるというのである。

Edgeは追加されていないのではない。見えないだけなのだ。えぇー・・・。

もっと正確に言えば、Gremlinのg.Eから参照できないというだけで、たとえばg.V.outEとかやると、g.Eに期待する結果と同じものが取得できたりする。

回避策

この状況を回避するためには、「見えないEdge」を作ってくれるおせっかいモードを以下のようにオフにすればよい。
g.setUseLightweightEdges(false)

これはaddEdgeするとき等、書き込む場合に効く設定なので、すでに「見えないEdge」を作ってしまった状態でこれを実行しても見えるようにはならない。
この設定を入れた状態でaddEdgeをすると、propertyが空でもg.Eで参照できるEdgeができるというわけだ。
また、この設定は現在のセッションにだけ有効なので、気になる場合には
g = new OrientGraph(...)
g.setUseLightweightEdges(false)

のようにGraphインスタンスの生成とセットにしておくと良いかもしれない。
ただし、propertyのないEdgeを大量に作成するようなスクリプトを流す場合は、この設定は入れないほうが速い。
でもそうすると作成されるのはLightWeightEdgeになっちゃうから痛し痒しである。


以上。なかなかやらかしてくれるわい。

2014年4月18日金曜日

[WWW2014] TwitterはSNSなのか情報基盤なのか

WWW2014のTwitterソーシャルグラフに関する論文を読んだよ。

Information Network or Social Network? The Structure of the Twitter Follow Graph

Twitterのフォロー関係をソーシャルグラフにしたときの各種特徴量を計測して、
その値がSNSっぽい値なのか、そこから外れているのかを評価していくというもの。

その中で、日本のユーザにだけすごく特徴的な結果が出ているものがあるらしいってので読んでみました。
論文の内容で気に止まったものをメモがてら書きます。

そもそもグラフとは


頂点とそれを結ぶ辺からなる情報構造のこと(グラフ理論 - Wikipedia)。

そしてグラフ構造で人付き合いのようすを表現したものがソーシャルグラフですね。

ユーザを頂点とし、フォローしあっているユーザを矢印で結ぶとTwitter上のソーシャルグラフができます。

評価の方法

分析対象データは2012年下半期のある時点のフォロー関係をスナップショットとして保存したもの。
分析処理はTwitter社内のHadoopクラスタでPigを使って実行した。
Pigか。。。統計量の算出とかがメインで、グラフのトラバースとかはやってないんだろうな。

参照する先行研究としては
(どれも読んでません!!)
など。TwitterのソーシャルグラフはFacebookやMSNメッセンジャーと比べてどうなのか、それは「SNSっぽい」値なのか、を検討しています。

フォロー/フォロワー/相互フォロー数による分析

フォロー/フォロワー/相互フォロー数の規模ごとにどれくらいのユーザが分布しているのかを分析しています。

Twitterはスパムアカウント対策として、2000件以上フォローするにはフォロワーが2200人以上必要という仕様になっているんだそうな。
ということで、フォロー数の分布は2000人の所でがっくりとギャップができています。
3つの分布を比べると、だいたいのユーザはフォロー数のほうがフォロワー数よりも多いらしい。まぁ、そうですわな。。。

論文ではこのセクションを「ソーシャルグラフにしてはフォロー/被フォローの規模が多きすぎるのでSNSっぽくない」と結論づけています。
Facebookについて語る時にも言われることなんですが、人間が友人関係をきちんと保てるのは同時に150人が限界、それはSNS上でも同じ、ということで、
フォロー何千というユーザがもりもりいるような状態はSNSっぽくないということのようです。

ただ、データの載ってる表から分位数のところを見ると、75%のユーザはフォローが121以下、相互フォローは50以下ということになるので、充分SNSっぽい数字じゃね?と思うわけですが。

クラスタ係数による分析

クラスタ係数とは、自分の友達が友達同士である割合のことです。
厳密には、共通の頂点Aと繋がっている頂点Bと頂点Cがあったとき、頂点Bと頂点Cが繋がっている割合ということですね。
これを折れ線グラフにしたものがおもしろいんです。


論文より引用

ふつうの人間関係であれば、自分の友達が友達同士である割合は高いと思います。
でもTwitterにはフォロー/フォロワーが鬼のようにいる人もいます。Twitterを「個人のつながり」のツールとして使ってない人々、たとえばパリスヒルトンやらオバマ大統領やら、企業のアカウントやら、そいういうアカウントのことです。

ということで、相互フォローの規模が大きいユーザほど、必然的にクラスタ係数も落ちてきてしまいます。
ところが日本のユーザに限っては、相互フォロー数が100から1000に伸びるにつれてクラスタ係数が上がるんですね(グラフ(b)の緑色の系列)。
つまり日本にだけ、みっしりしたアルファツイッタラークラスタ的なものがあり、それがグラフのしっぽを押し上げているということです。

これのせいで全体の値(グラフ(a))もちょっと形が変わってしまっています。
他にも論文では、

  • 日本人は、アメリカ・ブラジルと比較してクラスタ係数が高い
  • ていうか日本人は地球上で一番クラスタ係数が高い
  • 日本人はリフォロー率が高い

ということを指摘しています。

なお、論文中でクラスタ係数を評価して得られた結論は、「TwitterはSNSっぽい」だったようです。


結論

その他の特徴量はざっくり飛ばします。
いろいろ評価した結果、「TwitterはSNSっぽい」となる指標もあれば「SNSっぽくない」となる指標もでてきます。

全体の結果を受けて論文では、Twitterユーザがフォロー/フォロワーを増やしていく様子として以下のような行動を想定したようです(おおいに意訳含む)。

  • Twitterをはじめたてのユーザはなんだかよくわからないので有名なアカウントをフォローする。
  • いくらか歴が長くなってくると、アルファツイッタラーだからといってホイホイフォローするようなことはなくなる。
  • そのうち知人と「Twitterやってんの?フォローしてよ!」みたいなことになったり、自分の居心地のいいクラスタを見つけてそこに溶けこむようになるSNS的な使い方がはじまる。
  • やがて、有名人だからといってフォローしたアカウントはフォローから外す。

論文をきっちりと読み込んでないのでわかんないのですが、この想定がデータだけから出てきたんだったらすごいですね。「たしかにそうだなあ」という感じしますよね。

私はTwitterを始めたきっかけがモブストライクというソシャゲーだったので、初期のフォロワーはモブストライクで仲間がほしい同士の普通の知らない人だったわけですがw

フォロー関係だけでなくリストに入れているかどうかというのも分析すると面白そうだと思いますね。きっとリストでできる関係は、SNSというよりは情報基盤的な形をしているんじゃないかと思います。

以上。それでは。