ナード戦隊データマン

データサイエンスを用いて悪と戦うぞ

WikipediaのカテゴリーグラフをNetworkXで構築して概念の一般性を測る

Wikipediaでは、categorylinksテーブルがあり、このテーブルはページIDと関連するカテゴリーの情報が格納されています。pageテーブルからカテゴリーを表すページを取得すれば階層的なグラフ構造が作れるので、ここではNetworkXを用いて概念の一般性を測ります。

事前準備

page.sql.gzとcategorylinks.sql.gzを以下からダウンロードしてください。

https://dumps.wikimedia.org/enwiki/

一般性とは

一般性は、そのカテゴリーがどのぐらい抽象的なのか意味します。これは、Category:Contentsというルートノードからの最短距離として測ることができます。

pageテーブルからどのようにページを取得するのか

pageテーブルの2番目のカラムはnamespaceを表しますが、この番号が14となっているものが、カテゴリーを意味しています。つまり、namespace=14となるページIDとタイトルを取得します。

コード

import re
import pandas as pd
from tqdm import tqdm

def dumpiter(dumpfile):
    regex = re.compile(r"\(([0-9]+),([0-9]+),'(.+?)'")
    with open(dumpfile) as f:
        the_iter = re.finditer(regex, f.read())
    return the_iter

def transform(the_iter):
    out = []
    for d in tqdm(the_iter):
        if int(d.group(2)) == 14:
            out.append((d.group(1), d.group(3)))
    return pd.DataFrame(out, columns=["pid", "title"])

if __name__ == '__main__':
    transform(
        dumpiter("../dumps/enwiki-20180120-page.sql")
    ).to_csv("features/category_ids.csv", index=False)

categorylinksからエッジを取得

pageから取得したカテゴリーはノードのリストです。一方で、categorylinksから取得するのはエッジです。エッジとは、ノードとノードのつながりを意味します。

コード

import pickle
import pandas as pd
from tqdm import tqdm

def prepare(categoryfile):
    df = pd.read_csv(categoryfile)
    cid2title = {str(d['pid']):str(d['title']) for i,d in df.iterrows()}
    return cid2title

def myreadlines(f, newline):
    buf = ""
    while True:
        while newline in buf:
            pos = buf.index(newline)
            yield buf[:pos]
            buf = buf[pos + len(newline):]
        chunk = f.read(4096)
        if not chunk:
            yield buf
            break
        buf += str(chunk)

def solve(categorylinksfile, cid2title):
    first = True
    edges = []
    with open(categorylinksfile, 'rb') as f:
        for line in tqdm(myreadlines(f, ",(")):
            if first:
                first = False
                continue
            try:
                tmp = line.split(",")
                parent_id = str(tmp[0])
                category = str(tmp[1][1:-1])
            except:
                continue

            try:
                edges.append((cid2title[parent_id], category))
            except:
                pass
            
    return edges

def save(edges, efile):
    with open(efile, "wb") as f:
        pickle.dump(edges, f)

def run_it(categoryfile, categorylinksfile, efile):
    save(solve(categorylinksfile, prepare(categoryfile)), efile)

if __name__ == "__main__":
    run_it(
        "features/category_ids.csv",
        "../dumps/enwiki-20180120-categorylinks.sql",
        "category_edges.pickle"
    )

NetworkXにノードとエッジを渡してグラフを作る

NetworkXにノードとエッジを渡してグラフを作り、一般性を求めてみましょう。

In[1]:

import pickle
import pandas as pd

nodes = pd.read_csv("features/category_ids.csv")['title'].unique().tolist()
with open("features/category_edges.pickle", 'rb') as f:
    edges = pickle.load(f)

In[2]:

import networkx as nx
G = nx.Graph()
G.add_nodes_from(nodes)
G.add_edges_from(edges)

In[3]:

for obj in ["Articles", 'Countries', "Africa"]:
    print(nx.shortest_path_length(G, source='Contents', target=obj))

Out[3]:

3
4
5

In[4]:

nx.shortest_path(G, source='Contents', target='Algebra')

Out[4]:

['Contents',
 'Wikipedia_administration',
 'Categories_requiring_diffusion',
 'Algorithms',
 'Computer_algebra',
 'Algebra']

おわりに

ここでは、特定のカテゴリーの一般性を求めましたが、categorylinksはページIDとカテゴリーが紐付いているので、任意のページの一般性を紐付いたカテゴリーを基に求めることも可能です。参考に挙げている論文の中では幅優先探索が用いられている旨が書かれていますが、NetworkXを用いたほうが効率性は増します。

参考

https://dl.acm.org/citation.cfm?id=2631802