สร้าง Dynamic Programming Language Influence Graph ด้วย Gephi และ Sigma.js

Network Visualization Tutorial ด้วย Gephi และ Sigma.js

Preview สิ่งที่เราจะทำวันนี้: Programming Languages Influence Graph สำรวจความสัมพันธ์ "Design Influence" ระหว่าง 250+ Programming Languages มาและปัจจุบัน!

Your Turn!

โลก Hyper-connected วันนี้ Networks เป็น Ubiquitous Aspect ของชีวิตสมัยใหม่

ดูต้นวันของผม: ใช้ London Transport Network เดินทางเข้าประชุม แล้วเข้า Branch ร้านกาแฟโปรด ใช้ Chromebook เชื่อม Wi-Fi Network ต่อมา Login Social Networking Sites ที่ใช้บ่อย

ไม่อาจปฏิเสธ บริษัทที่มีอิทธิพลมากที่สุดในหลายทศวรรษ สำเร็จเพราะ Power of Networks

Facebook, Twitter, Instagram, LinkedIn และ Social Media Platforms อื่นๆ พึ่งพา Small-world Properties ของ Social Networks เชื่อม Users กับกัน (และ Advertisers) ได้มีประสิทธิภาพ

Google สำเร็จมากจาก Early Dominance Search Engine Market ส่วนหนึ่งจากความสามารถ Return Relevant Results ด้วย Page Rank Network Algorithm

Amazon Distribution Network ประหยัด Same-day Delivery ใน Major Cities บางแห่ง

Networks สำคัญใน AI และ ML Neural Networks Active Research Field Feature Detection Algorithms ใน Computer Vision พึ่ง Networks Model ภาพต่างๆ

Scientific Phenomena หลากหลาย เข้าใจได้ใน Network Models: Quantum Mechanics, Biochemical Pathways, Ecological และ Socio-economic Systems

ด้วย Importance ที่ปฏิเสธไม่ได้ เราจะเข้าใจ Networks และ Properties ดีขึ้นยังไง?

Mathematical Study ของ Networks เรียกว่า "Graph Theory" เป็นหนึ่งใน Branches of Mathematics ที่ Accessible บทความนี้ Aim ให้ Introduction สมมติ Prior Knowledge/Experience น้อย

เราจะใช้ Python 3.x และ Open-source Software ชื่อ Gephi สร้าง Network Visualization ของ Programming Languages ที่เชื่อมกันโดย Influence

But First…

Network คืออะไรจริงๆ?

ตัวอย่างด้านบนให้ Clues Transport Networks = Destinations เชื่อมด้วย Routes Social Networks = Individuals เชื่อมผ่าน Relationships Google Search Algorithms ประเมิน "Rank" ของ Webpages ดูว่า Pages ไหน Link ไปอีก Pages

โดยทั่วไป Network คือ System ใดๆ ที่อธิบายได้ในรูป Nodes และ Edges หรือพูดง่ายๆ "Dots and Lines"

Systems บางอย่าง Abstract ในรูปนี้ได้ง่าย Social Networks คลาสสิก Computer Filesystems อีกอย่าง - Folders/Files ลิงก์ด้วย Parent/Child Relationships

แต Real Power ของ Networks มาจาก: Systems หลายมาก Abstract และ Model ใน Network Terms ได้ แม้ตอนแรกไม่ชัดเจน

Representing Networks

ต้องไปไกลกว่า Pen-and-paper Sketches เพื่อ Analyze/Describe Networks Mathematically จะเปลี่ยน Pictures of Dots and Lines เป็น Numbers ที่ Crunch ได้ยังไง?

Solution หนึ่ง: วาด Adjacency Matrix Represent Network

Matrices อาจดู Intimidating ถ้าไม่คุ้น แต่มองว่าเป็น Grids of Numbers ใช้ Calculations หลายอย่างพร้อมกัน ตัวอย่าง:

 Python Java Scala C#
Python 0 1 0 0
Java 0 0 0 1
Scala 0 1 0 0
C# 0 1 0 0

ใน Matrix Intersection แต่ละ Row/Column เป็น 0 หรือ 1 ขึ้นอยู่กับว่า Languages เหล่านั้น Link กันหรือไม่ Check กับ Illustration ด้านบนได้

Adjacency Matrix ดีสำห Most Purposes แต Computational Perspective อาจ Cumbersome

แม้ Nodes แค่ 1000 Elements ใน Matrix จะ 1,000,000 (1000²)

Real-world Systems หลายอย่าง Yield Sparse Networks Nodes ส่วนใหญ่ Connect เพียง Proportion เล็กของ Others

ถ้า Represent 1000-node Sparse Network เป็น Adjacency Matrix ใน RAM จะมี 1,000,000 Bytes ส่วนใหญ่เป็น Zeros ต้องมีวิธี Efficient กว่า

Alternative: ใช้ Edge Lists แทน คือ List ของ Node Pairs ที่ Link กัน

ตัวอย่าง Programming Languages Network ด้านบน Represent ได้:

Java, Python
Java, Scala
Java, C#
C#, Java

Networks ใหญ่ Computationally Efficient มากกว่า และ Generate Adjacency Matrix จาก Edge List ได้ (Vice Versa) ไม่ต้องเลือกอย่างใดอย่างหนึ่ง

อีกวิธี: Adjacency Lists List ทุก Node ตามด้วย Nodes ที่ Link ไป ตัวอย่าง:

Java: Python, Scala, C#
C#: Java

Collecting Data, Making Connections

Network Model/Visualization จะดีเท่ากับ Data ที่สร้างมัน ต้อง Ensure Data Accurate/Complete และ Justify Means ของ Inferring Edges ระหว่าง Nodes

ในหลายมุมมอง นี่คือ THE Critical Step Analysis และ Inferences ต่อไป Depend On Justify "Linkage Criterion"

ตัวอย่าง Social Network Analysis Link People ว่าติดตามกันบน Social Media Molecular Biology Link Genes จาก Co-expression

วิธี Link Nodes บ่อยครั้ง Allow Weights ให้ Edges Measure "Strength"

ตัวอย่าง Online Retail Link Products จาก Purchase Frequency Products ซื้อร่วมกันบ่อย = Higher Weighted Edge Products ซื้อร่วมกันนานๆ = Lower Weight Products ซื้อร่วมกันไม่เกิน Chance = ไม่ Link

Methods Linking Nodes Sophisticated ได้เท่าไหร่ก็ได้

แต่ Tutorial นี้ใช้ Simpler Means เชื่อม Programming Languages เราจะพึ่ง Wikipedia Accuracy

สำหเรา Should Be Fine Wikipedia Success = Must Doing Something Right Open-source Collaborative Method เขียน Articles ควรให้ Objectivity ระดับหนึ่ง

เพิ่ม Page Structure Consistent ทำให้ Convenient Playground ลอง Web-scraping Techniques

Bonus: Wikipedia API Extensive/Well-documented ทำ Information Retrieval ง่ายขึ้น เริ่มกันเลย

Step 1 — Installing Gephi

Gephi Available Linux, Mac, Windows ดาวน์โหลดได้ที่นี่

โปรเจกต์นี้ผมใช้ Lubuntu Ubuntu/Debian Follow Steps ด้านล่างได้ ไม่ใช่ Installation Process คล้ายๆ กับที่คุ้นเคย

Download Latest Version (v.0.9.1 ตอนเขียน) สำห System Extract Files

cd Downloads
tar -xvzf gephi-0.9.1-linux.tar.gz
cd gephi-0.9.1/bin
./gephi

อาจต้องเช็ค Java JRE Version Gephi ต้องการ Recent Version Lubuntu Fresh Install ผมแค่ Install Default-jre ทำงานได้เลย

apt install default-jre
./gephi

อีก Step หนึ่งก่อนพร้อม: Export Graph ไป Web ใช้ Sigma.js Plugin สำห Gephi

จาก Menu Bar Gephi เลือก "Tools" → "Plugins"

Click "Available Plugins" Tab Select "SigmaExporter" (ผมติดตั้ง JSON Exporter ด้วย เพราะ Useful Plugin)

Hit "Install" Walk Through Process Restart Gephi เสร็จ

Step 2 — Writing the Python Script

Tutorial ใช้ Python 3.x + Modules ใช้ pip Install:

pip3 install wikipedia

Directory ใหม่ สร้างไฟล์ script.py เปิดใน Code Editor/IDE โครงสร้างหลัก:

1. List Programming Languages ที่จะ Include
2. Loop List ดึง HTML ของ Wikipedia Article แต่ละภาษา
3. Extract List ภาษาที่แต่ละภาษา Influence นี่คือ Linkage Criterion แบบ Rough-and-ready
4. Grab Metadata แต่ละภาษา
5. Write Data ทั้งหมดลง .csv File

Full Script ใน Gist นี้

Import Modules

ใน script.py Import Modules:

import csv
import wikipedia
import urllib.request
from bs4 import BeautifulSoup as BS
import re

เริ่ม List Nodes Include Wikipedia Module ทำให้ Access Wikipedia API Super Easy

เพิ่ม Code:

pageTitle = "List of programming languages"
nodes = list(wikipedia.page(pageTitle).links)
print(nodes)

Save และ Run Script จะ Print Links ทั้งหมดจาก Wikipedia Article "List of programming languages" Nice!

แต่ควร Manual Inspect Auto-collected Data Glance จะเห็น นอกจาก Programming Languages จริง Script ก็ดึง Extra Links มาด้วย

ตัวอย่าง: "List of markup languages", "Comparison of programming languages" และอื่นๆ

Gephi ให้ Remove Nodes ที่ไม่ต้องการ แต Clean Data ก่อนดีกว่า ประหยัดเวลา

removeList = [
    "List of", "Lists of", "Timeline", "Comparison of",
    "History of", "Esoteric programming language"
]
nodes = [i for i in nodes if not any(r in i for r in removeList)]

Lines นี้ Define Substrings ที่จะ Remove Script Loop Data Remove Elements ที่มี Unwanted Substrings

ใน Python ใช้ 1 Line!

Helper Functions

Scrape Wikipedia สร้าง Edge List (และ Collect Metadata) 定義 Functions

Grabbing HTML

Function แรก ใช้ BeautifulSoup ดึง HTML แต่ละ Programming Language Page

base = "https://en.wikipedia.org/wiki/"
def getSoup(n):
    try:
        with urllib.request.urlopen(base+n) as response:
            soup = BS(response.read(), 'html.parser')
            table = soup.find_all("table", class_="infobox vevent")[0]
            return table
    except:
        pass

Function นี้ใช้ urllib.request ดึง HTML ที่ base + "programming language"

Pass ให้ BeautifulSoup Parse HTML 成 Object Search ได้

用 find_all() Extract HTML Element ที่สนใจ

ที่นี่คือ Summary Table บนสุด แต่ละ Programming Language Article Identify ยังไง?

วิธีง่าย: เยี่ยม Programming Language Page ใช้ Browser Dev Tools Inspect Elements

Summary Table มี HTML Tag <table> CSS Classes "infobox" และ "vevent" ใช้ Identify Table ใน HTML

ระบุ Arguments:

• "table"
• class_="infobox vevent"

find_all() คืน List Elements Match Criteria 要 Specify Element 加 Index [0] สำเร็จ Return table Object ไม่งั้น Return None

Automated Data Collection ต้อง Handle Exceptions ดี ไม่งั้น Best Case Script Crash Restart Worst Case Dataset รidden Inconsistencies/Errors Nightmare Down the Line

Retrieve Metadata

Function ถัดไป ใช้ table Object หา Metadata ที่นี่ หา Year ภาษา First Appeared

def getYear(t):
    try:
        t = t.get_text()
        year = t[t.find("appear"):t.find("appear")+30]
        year = re.match(r'.*([1-3][0-9]{3})', year).group(1)
        return int(year)
    except:
        return "Could not determine"

Function สั้นนี้ รับ table Object ใช้ get_text() BeautifulSoup 产出 String

สร้าง Substring year เอา 30 Characters หลัง "appear" ครั้งแรก String นี้ควรมี Year First Appeared

Extract Year 用 Regular Expression (courtesy of re Module) Match Digits เริ่ม 1-3 ตามด้วย 3 Digits

re.match(r'.*([1-3][0-9]{3})', year)

สำเร็จ Return year as Integer ไม่งั้น Return "Could not determine" อาจ Scrape Metadata เพิ่ม: Paradigm, Designer, Typing Discipline

Collecting Links

Function อีกตัว Feed table Object ภาษา หวังได้ List Programming Languages อื่น

def getLinks(t):
    try:
        table_rows = t.find_all("tr")
        for i in range(0, len(table_rows)-1):
            try:
                if table_rows[i].get_text() == "\nInfluenced\n":
                    out = []
                    for j in table_rows[i+1].find_all("a"):
                        try:
                            out.append(j['title'])
                        except:
                            continue
                    return out
            except:
                continue
        return
    except:
        return

Woah Nesting เยอะ… ทำอะไรอยู่จริง?

Function ใช้ Fact: table Objects มี Consistent Structure Info ใน Table อยู่ใน Rows (HTML Tag <tr>) Row หนึ่งมี Text "\nInfluenced\n" ส่วนแรกหา Row นี้

เจอ Row นี้ Next Row น่าจะมี Links Programming Languages ที่ Influenced โดย Current One หา Links 用 find_all("a") Argument "a" = HTML Tag <a>

แต่ละ Link j Append ["title"] Attribute ลง List out เน้น ["title"] เพราะ Match Exactly ชื่อภาษาใน nodes

ตัวอย่าง Java ใน nodes เป็น "Java (programming language)" ต้องใช้ชื่อนี้ Exact Throughout Dataset

สำเร็จ getLinks() Return List Programming Languages ส่วนที่เหลือ Exception Handling

edgeList = [["Source,Target"]]
meta = [["Id","Year"]]

for n in nodes:
    try:
        temp = getSoup(n)
    except:
        continue
    try:
        influenced = getLinks(temp)
        for link in influenced:
            if link in nodes:
                edgeList.append([n+","+link])
                print([n+","+link])
        except:
            continue
        year = getYear(temp)
        meta.append([n, year])
    except:
        continue

with open("edge_list.csv", "w") as f:
    wr = csv.writer(f)
    for e in edgeList:
        wr.writerow(e)
with open("metadata.csv", "w") as f2:
    wr = csv.writer(f2)
    for m in meta:
        wr.writerow(m)