今日は、ソーシャルネットワーク分析（ SNA ）のタスクを詳しく調べ、ビッグデータ分析用に設計されたApache Sparkライブラリのレビューも終了します。 つまり、以前の記事（ 1と2 ）で約束したように、グラフ分析を目的としたApache Sparkコンポーネントの1つ、 GraphXを検討します。 グラフの分散ストレージとそれらの計算がこのライブラリにどのように実装されているかを理解しようとします。 また、スパム検索、検索エンジンのランキング、ソーシャルネットワーク上のコミュニティの強調表示、オピニオンリーダーの検索など、このライブラリの実際の使用方法を具体的な例で示します。これはグラフ分析手法の完全なアプリケーションリストではありません。
それでは、（グラフ理論に没頭していない人のために）この記事で扱う主なオブジェクトを思い出し、アルゴリズムとこの背後にあるすべての美しい数学について詳しく見てみましょう。
グラフ理論、ランダムグラフ、およびWebグラフ
おそらく、このセクションで一番いいのは、読者に私の科学顧問のアンドレイ・ミハイロヴィチ・ライゴロツキーによる素晴らしいビデオ講義やパンフレットを見てもらうことです。 また、 これまたはそれを見ることを強くお勧めします。 さらに良いことに、Andrei MikhailovichのCourseraのコースにサインアップしてください。 したがって、ここでは基本的な概念のみを示し、詳細には触れません。
グラフはG =（V、E）のペアです。ここで、 Vは頂点のセット（たとえば、インターネット上のサイト）、 Eは頂点を接続するエッジのセット（それぞれ、サイト間のリンク）です。 長年分析されてきたわかりやすい構造。 しかし、実際には、実際のネットワークを分析するときに疑問が生じます-このグラフはどのように構築されますか？ 新しいサイトがインターネットに表示されたとしましょう-そもそもだれにリンクするのか、平均していくつの新しいリンクが表示されるのか、このサイトは検索結果でどれだけランク付けされるのでしょうか？
この問題（ Webグラフのデバイス）の人々は、インターネットの出現以来ほとんど対処してきました。 この間、 多くのモデルが発明されました。 少し前まで、 Yandexで一般化モデルが提案され、 その特性も調査されました。
グラフがすでに提供されている場合、そのプロパティとグラフでのさらなる計算が明確に定義されています。 たとえば、特定の頂点の程度を自分自身（ソーシャルネットワーク上の人の友人の数）で調べたり、特定の頂点間の距離（ネットワークで特定の2人が知っているハンドシェイクの数）を測定したり、接続性のコンポーネント（人の間の「つながり」に応じて、人のグループ）を計算したり、任意の2人がよく知っている）など。
古典的なアルゴリズムは次のとおりです。
PageRankは、1998年にGoogleによって提案されたグラフの頂点の「権限」を計算するためのよく知られたアルゴリズムであり、検索結果のランク付けに長い間使用されてきました。
（強く）接続されたコンポーネントの検索は、特定のサブセットの任意の2つの頂点間にパスが存在し、異なるサブセットの頂点間にパスがないように、グラフ頂点のサブセットを検索するためのアルゴリズムです。
グラフ内の最短パスのカウント -頂点のペア間、特定の2つの頂点間、重み付きグラフおよびその他の設定で
三角形の数のカウント、クラスタリング、頂点の度数の分布、グラフ内のクリック検索などのほかに。 ほとんどのアルゴリズムは反復的であり、したがって、このコンテキストでは、GraphXライブラリはRAMにデータをキャッシュするという事実により、非常によく表示されます。 次に、このライブラリが提供する機会を検討します。
スパークグラフ
GraphXは最初のグラフ分析ツールではなく、唯一のグラフ分析ツールではないことに注意してください（よく知られているツールは、たとえば、 GraphLab-現在のDato.comまたはPregel計算モデル-APIはGraphXで部分的に使用されています）。この投稿の執筆は、ライブラリがまだ開発中であり、その機能はそれほど優れていません。 それでも、実際に発生するほとんどすべてのタスクについて、GraphXは何らかの方法でアプリケーションを正当化します。
GraphXはまだPythonをサポートしていないので、 SparkContextが既に作成されていることを前提として、Scalaでコードを記述します（以下のコードで-変数sc ）。 以下のコードのほとんどは、ドキュメントとオープンソースの資料から引用されています。 したがって、まず最初に、必要なすべてのライブラリをダウンロードします。
import org.apache.spark.graphx._ import org.apache.spark.rdd.RDD
Sparkでは、グラフの概念はいわゆるプロパティグラフの形式で実装されます。これは、頂点とエッジにラベル（追加情報）を持つマルチグラフです。 マルチグラフは、 複数のエッジ （2つの頂点間に複数のエッジがある場合があります）、 ループ （頂点からそれ自体へのエッジ） が許可される有向 （エッジに方向がある）グラフです。 すぐに、指向グラフの場合、 着信次数 （着信エッジの数）や発信次数 （頂点から発生するエッジの数）などの概念が定義されると言います。 特定のグラフを作成する方法の例を見てみましょう。
グラフ構築
ローカルプログラムから頂点とエッジの配列を渡すことにより、 Graphコンストラクターを使用してグラフを作成できます（.parallelize（）関数を使用してRDDにすることを忘れないでください）。
val vertexArray = Array( (1L, ("Alice", 28)), (2L, ("Bob", 27)), (3L, ("Charlie", 65)), (4L, ("David", 42)), (5L, ("Ed", 55)), (6L, ("Fran", 50)) ) val edgeArray = Array( Edge(2L, 1L, 7), Edge(2L, 4L, 2), Edge(3L, 2L, 4), Edge(3L, 6L, 3), Edge(4L, 1L, 1), Edge(5L, 2L, 2), Edge(5L, 3L, 8), Edge(5L, 6L, 3) ) val vertexRDD = sc.parallelize(vertexArray) val edgeRDD = sc.parallelize(edgeArray) val graph = Graph(vertexRDD, edgeRDD)
または、たとえばHDFSにあるいくつかのデータに基づいて頂点とエッジを最初に構築する必要がある場合は、最初に元のデータ自体を処理する必要があります（多くの場合、 .map（）変換の場合）。 たとえば、ウィキペディアの記事が（id、title）として保存され、記事間のリンクがペアとして保存されている場合、グラフは非常に簡単に構築されます-これを行うには、最初のケースでタイトルからidを分離し、エッジ自体を構築します（これにはEdgeコンストラクターがあります） -2番目のケースでは、出力時に、 Graphコンストラクターに渡すことができる頂点とエッジのリストを取得します。
val articles = sc.textFile("articles.txt") val links = sc.textFile("links.txt") val vertices = articles.map { line => val fields = line.split('\t') (fields(0).toLong, fields(1)) } val edges = links.map { line => val fields = line.split('\t') Edge(fields(0).toLong, fields(1).toLong, 0) } val graph = Graph(vertices, edges, "").cache()
グラフを作成した後、いくつかの特性を計算し、上記のアルゴリズムを含むアルゴリズムを実行できます。 続行するまで、ここでは、頂点とエッジの概念に加えて、トリプレット（ Triplet ）の概念も実装されていることに注意してください。これは、ある意味で、オブジェクトのエッジ（ Edge ）それに隣接するピーク。
グラフ計算
注目すべき事実は、ほとんどのパッケージで（そしてGraphXも例外ではありません）-グラフを作成した後、その上で計算を行い、標準アルゴリズムを実行することも簡単になります。 実際、グラフ自体の計算方法は非常によく研究されており、特定のアプリケーションで最も難しいのは、グラフを決定するルール、つまり、頂点とエッジが何であるかを決定するルールです（どのような基準で実行されるべきか）。 以下に、コメント付きのGraphオブジェクトで使用できるメソッドのリストを示します。
class Graph[VD, ED] { // val numEdges: Long // val numVertices: Long // val inDegrees: VertexRDD[Int] // val outDegrees: VertexRDD[Int] // val degrees: VertexRDD[Int] // // , val vertices: VertexRDD[VD] val edges: EdgeRDD[ED] val triplets: RDD[EdgeTriplet[VD, ED]] // ( ) def mapVertices[VD2](map: (VertexID, VD) => VD2): Graph[VD2, ED] def mapEdges[ED2](map: Edge[ED] => ED2): Graph[VD, ED2] def mapEdges[ED2](map: (PartitionID, Iterator[Edge[ED]]) => Iterator[ED2]): Graph[VD, ED2] def mapTriplets[ED2](map: EdgeTriplet[VD, ED] => ED2): Graph[VD, ED2] // def reverse: Graph[VD, ED] // - def subgraph( epred: EdgeTriplet[VD,ED] => Boolean = (x => true), vpred: (VertexID, VD) => Boolean = ((v, d) => true)) : Graph[VD, ED] // , def groupEdges(merge: (ED, ED) => ED): Graph[VD, ED] // // def pageRank(tol: Double, resetProb: Double = 0.15): Graph[Double, Double] // PageRank def connectedComponents(): Graph[VertexID, ED] // def triangleCount(): Graph[Int, ED] // def stronglyConnectedComponents(numIter: Int): Graph[VertexID, ED] // }
現在のSparkXの実装には実装されたアルゴリズムがかなり含まれているため、Apache Sparkの代わりに上記の既知のパッケージを使用することは依然として重要ですが、GraphXは将来的に大幅に改善され、RAMにデータをキャッシュする可能性があるため、おそらくグラフの問題で十分な人気を得ています。 結論として、グラフ法を適用する必要がある実際の問題の例を示します。
実用的なタスク
上記のように、実際の問題の主な問題は、複雑なアルゴリズムを実行することではありません。つまり、グラフの正しい定義、適切な前処理、問題を古典的な解決済みのものに減らすことです。 例を挙げて考えてみましょう。読者に反省のために多数の質問を残しています。
新しいrib骨の外観の予測（リンク予測）
問題は非常に一般的です-ある時点までグラフに追加されるエッジのシーケンスが与えられます。 グラフに将来表示されるエッジを予測する必要があります。 実生活の観点から見ると、このタスクはレコメンダーシステムの一部です。たとえば、2人のソーシャルユーザー間のつながり（「友情」）を予測します。 ネットワーク。 実際、この問題では、任意に選択された頂点のペアごとに、将来的にそれらの間にエッジが存在する確率を予測する必要があります-ここでは、記号と頂点の説明を操作する必要があります。 たとえば、兆候の1つが友人の集合の交差点、またはジャカードメジャーである場合があります。 読者は、頂点間の類似性の可能な指標について考え、コメントに彼自身のバリエーションを書くように招待されています。
ソーシャルネットワークでのコミュニティのハイライト
特定のタスクに起因するのが難しいタスク。 多くの場合、「グラフ上のクラスタリング」というタスクのコンテキストで考慮されます。 この問題を解決する方法はたくさんあります-正しく定義された頂点のサブセットで接続されたコンポーネント（アルゴリズムについては前述）を選択することから、目的のコンポーネントが残るまでグラフからエッジを連続的に削除することです。 ここでも、ネットワーク上で強調したいコミュニティを最初に理解することが非常に重要です。 最初に、頂点とエッジの説明を使用して、結果のサブグラフでコミュニティ自体を区別する方法を検討します。
最短グラフ距離
このタスクも古典的であり、たとえば、同じYandex.Metroまたは特定のグラフの最短経路を見つけるのに役立つ他のサービスに実装されます-都市のポイント間の接続のグラフまたは知人のグラフであるかどうか。
または、たとえば携帯電話会社が簡単に直面できるタスク：
オンラインのオピニオンリーダーを特定する
たとえば、モバイルインターネットなどの新しいオプションを宣伝するために、広告予算を最適化するために、ある意味で外部の注意に囲まれている人を選びたいと思います。 私たちの用語では、これらはネットワーク上で大きな権限を持つグラフの頂点です。したがって、このタスクは、グラフが正しく構築されるとPageRank問題に帰着します。
そこで、実際に発生する可能性のあるグラフ分析の典型的な応用問題と、それらを解決するために使用できるツールの1つを調べました。 これで、Apache Sparkライブラリのレビュー、および実際にツールの概要が終了しました。今後、アルゴリズムと特定のタスクにさらに焦点を当てます。