دليل مستخدم GraphFrames - Scala

توضح هذه المقالة أمثلة من دليل مستخدم GraphFrames.

import org.apache.spark.sql._
import org.apache.spark.sql.functions._
import org.graphframes._

إنشاء GraphFrames

يمكنك إنشاء GraphFrames من الذروة وحافة DataFrames.

• Vertex DataFrame: يجب أن يحتوي إطار بيانات الذروة على عمود خاص يسمى id يحدد معرفات فريدة لكل ذروة في الرسم البياني.
• Edge DataFrame: يجب أن يحتوي Edge DataFrame على عمودين خاصين: src (معرف ذروة المصدر للحافة) و dst (معرف ذروة الوجهة للحافة).

يمكن أن يحتوي كلا DataFrames على أعمدة أخرى عشوائية. يمكن أن تمثل هذه الأعمدة سمات الذروة والحافة.

إنشاء الرؤوس والحواف

// Vertex DataFrame
val v = spark.createDataFrame(List(
  ("a", "Alice", 34),
  ("b", "Bob", 36),
  ("c", "Charlie", 30),
  ("d", "David", 29),
  ("e", "Esther", 32),
  ("f", "Fanny", 36),
  ("g", "Gabby", 60)
)).toDF("id", "name", "age")
// Edge DataFrame
val e = spark.createDataFrame(List(
  ("a", "b", "friend"),
  ("b", "c", "follow"),
  ("c", "b", "follow"),
  ("f", "c", "follow"),
  ("e", "f", "follow"),
  ("e", "d", "friend"),
  ("d", "a", "friend"),
  ("a", "e", "friend")
)).toDF("src", "dst", "relationship")

دعونا ننشئ رسما بيانيا من هذه الرؤوس وهذه الحواف:

val g = GraphFrame(v, e)

// This example graph also comes with the GraphFrames package.
// val g = examples.Graphs.friends

استعلامات الرسم البياني الأساسي وDataFrame

توفر GraphFrames استعلامات رسم بياني بسيطة، مثل درجة العقدة.

أيضا، نظرا لأن GraphFrames تمثل الرسوم البيانية كأزواج من الذروة وإطارات بيانات الحافة، فمن السهل إجراء استعلامات قوية مباشرة على الذروة وإطارات بيانات الحافة. تتوفر DataFrames هذه كرؤوس وحقول حواف في GraphFrame.

display(g.vertices)

display(g.edges)

درجة الذروات الواردة:

display(g.inDegrees)

درجة الذروات الصادرة:

display(g.outDegrees)

درجة الذروات:

display(g.degrees)

يمكنك تشغيل الاستعلامات مباشرة على رؤوس DataFrame. على سبيل المثال، يمكننا العثور على عمر أصغر شخص في الرسم البياني:

val youngest = g.vertices.groupBy().min("age")
display(youngest)

وبالمثل، يمكنك تشغيل الاستعلامات على الحواف DataFrame. على سبيل المثال، دعنا نحسب عدد علاقات "المتابعة" في الرسم البياني:

val numFollows = g.edges.filter("relationship = 'follow'").count()

العثور على الشعار

بناء علاقات أكثر تعقيدا تتضمن الحواف والرؤوس باستخدام الزخارف. تعثر الخلية التالية على أزواج الذروات ذات الحواف في كلا الاتجاهين بينهما. والنتيجة هي DataFrame، حيث تكون أسماء الأعمدة مفاتيح متحركة.

راجع دليل مستخدم GraphFrame لمزيد من التفاصيل حول واجهة برمجة التطبيقات.

// Search for pairs of vertices with edges in both directions between them.
val motifs = g.find("(a)-[e]->(b); (b)-[e2]->(a)")
display(motifs)

نظرا لأن النتيجة هي DataFrame، يمكنك إنشاء استعلامات أكثر تعقيدا يمكن أن تكون أعلى الشعار. دعونا نجد جميع العلاقات المتبادلة التي يكون فيها شخص واحد أكبر من 30 عاما:

val filtered = motifs.filter("b.age > 30")
display(filtered)

استعلامات ذات حالة

معظم استعلامات الزخارف عديمة الحالة وسهلة التعبير، كما هو الحال في الأمثلة أعلاه. توضح الأمثلة التالية استعلامات أكثر تعقيدا تحمل الحالة على طول مسار في الشعار. عبر عن هذه الاستعلامات عن طريق الجمع بين البحث عن GraphFrame مع عوامل التصفية على النتيجة، حيث تستخدم عوامل التصفية عمليات التسلسل لإنشاء سلسلة من أعمدة DataFrame.

على سبيل المثال، افترض أنك تريد تحديد سلسلة من 4 رؤوس مع بعض الخاصية المحددة بواسطة تسلسل من الدالات. أي، بين سلاسل من 4 رؤوس a->b->c->d، حدد المجموعة الفرعية من السلاسل المطابقة لهذا عامل التصفية المعقد:

• تهيئة الحالة على المسار.
• تحديث الحالة استنادا إلى الذروة a.
• تحديث الحالة استنادا إلى الذروة b.
• الخ. ل c وd.
• إذا تطابقت الحالة النهائية مع بعض الشروط، فسيقبل عامل التصفية السلسلة.

توضح القصاصات البرمجية التالية هذه العملية، حيث نحدد سلاسل من 4 رؤوس بحيث تكون 2 من الحواف 3 على الأقل علاقات "صديق". في هذا المثال، الحالة هي العدد الحالي للحواف "الصديقة"؛ بشكل عام، يمكن أن يكون أي عمود DataFrame.

// Find chains of 4 vertices.
val chain4 = g.find("(a)-[ab]->(b); (b)-[bc]->(c); (c)-[cd]->(d)")

// Query on sequence, with state (cnt)
//  (a) Define method for updating state given the next element of the motif.
def sumFriends(cnt: Column, relationship: Column): Column = {
  when(relationship === "friend", cnt + 1).otherwise(cnt)
}
//  (b) Use sequence operation to apply method to sequence of elements in motif.
//      In this case, the elements are the 3 edges.
val condition = Seq("ab", "bc", "cd").
  foldLeft(lit(0))((cnt, e) => sumFriends(cnt, col(e)("relationship")))
//  (c) Apply filter to DataFrame.
val chainWith2Friends2 = chain4.where(condition >= 2)
display(chainWith2Friends2)

الرسوم البيانية الفرعية

يوفر GraphFrames واجهات برمجة التطبيقات لبناء الرسومات الفرعية عن طريق التصفية على الحواف والرؤوس. يمكن أن تتكون عوامل التصفية هذه معا. على سبيل المثال، يحتوي الرسم الفرعي التالي فقط على أشخاص أصدقاء وأكثر من 30 عاما.

// Select subgraph of users older than 30, and edges of type "friend"
val g2 = g
  .filterEdges("relationship = 'friend'")
  .filterVertices("age > 30")
  .dropIsolatedVertices()

عوامل تصفية ثلاثية معقدة

يوضح المثال التالي كيفية تحديد رسم فرعي استنادا إلى عوامل تصفية ثلاثية تعمل على حافة ورؤوسها "src" و"dst". يعد توسيع هذا المثال لتجاوز الثلاثيات باستخدام نماذج أكثر تعقيدا أمرا بسيطا.

// Select subgraph based on edges "e" of type "follow"
// pointing from a younger user "a" to an older user "b".
val paths = g.find("(a)-[e]->(b)")
  .filter("e.relationship = 'follow'")
  .filter("a.age < b.age")
// "paths" contains vertex info. Extract the edges.
val e2 = paths.select("e.src", "e.dst", "e.relationship")
// In Spark 1.5+, the user may simplify this call:
//  val e2 = paths.select("e.*")

// Construct the subgraph
val g2 = GraphFrame(g.vertices, e2)

display(g2.vertices)

display(g2.edges)

خوارزميات الرسم البياني القياسية

يصف هذا القسم خوارزميات الرسم البياني القياسية المضمنة في GraphFrames.

البحث عن النطاق الأول (BFS)

ابحث من "Esther" عن المستخدمين البالغين من العمر 32 عاما < .

val paths: DataFrame = g.bfs.fromExpr("name = 'Esther'").toExpr("age < 32").run()
display(paths)

قد يحد البحث أيضا من عوامل تصفية الحافة والحد الأقصى من أطوال المسار.

val filteredPaths = g.bfs.fromExpr("name = 'Esther'").toExpr("age < 32")
  .edgeFilter("relationship != 'friend'")
  .maxPathLength(3)
  .run()
display(filteredPaths)

المكونات المتصلة

حساب عضوية المكون المتصل لكل ذروة وإرجاع رسم بياني مع تعيين معرف مكون لكل ذروة.

val result = g.connectedComponents.run() // doesn't work on Spark 1.4
display(result)

المكونات المتصلة بقوة

حساب المكون المتصل بشدة (SCC) لكل ذروة وإرجاع رسم بياني مع كل ذروة معينة إلى SCC تحتوي على تلك الذروة.

val result = g.stronglyConnectedComponents.maxIter(10).run()
display(result.orderBy("component"))

نشر التسمية

قم بتشغيل خوارزمية نشر التسميات الثابتة للكشف عن المجتمعات في الشبكات.

يتم تعيين كل عقدة في الشبكة في البداية إلى مجتمعها الخاص. في كل خرافية، ترسل العقد انتماءها المجتمعي إلى جميع الجيران وتحديث حالتها إلى وضع الانتماء المجتمعي للرسائل الواردة.

LPA هي خوارزمية اكتشاف مجتمع قياسية للرسوم البيانية. إنه غير مكلف حسابيا، على الرغم من أن (1) التقارب غير مضمون و(2) يمكن للمرء أن ينتهي بحلول تافهة (تحدد جميع العقد في مجتمع واحد).

val result = g.labelPropagation.maxIter(5).run()
display(result.orderBy("label"))

الموقع

تحديد الذروات المهمة في رسم بياني استنادا إلى الاتصالات.

// Run PageRank until convergence to tolerance "tol".
val results = g.pageRank.resetProbability(0.15).tol(0.01).run()
display(results.vertices)

display(results.edges)

// Run PageRank for a fixed number of iterations.
val results2 = g.pageRank.resetProbability(0.15).maxIter(10).run()
display(results2.vertices)

// Run PageRank personalized for vertex "a"
val results3 = g.pageRank.resetProbability(0.15).maxIter(10).sourceId("a").run()
display(results3.vertices)

أقصر المسارات

يحسب أقصر المسارات إلى مجموعة معينة من رؤوس المعالم، حيث تحدد المعالم بواسطة معرف الذروة.

val paths = g.shortestPaths.landmarks(Seq("a", "d")).run()
display(paths)

عد المثلثات

يحسب عدد المثلثات التي تمر عبر كل ذروة.

import org.graphframes.examples
val g: GraphFrame = examples.Graphs.friends  // get example graph

val results = g.triangleCount.run()
results.select("id", "count").show()