Wiki Graph

위키 문서들의 링크 관계를 그래프로 구축하는 모듈. 위키의 핵심 가치는 문서 간 연결에 있으므로, 이 그래프는 관련 문서 추천, 고립 문서 탐지, 미작성 문서 우선순위 결정의 기반이 된다.

Backlink 대칭성

A → B 링크가 있으면, B의 backlinks에 A가 포함되어야 한다. 이 대칭 관계는 위키 그래프의 핵심 불변량이다.

Backlink가 정확해야 "이 문서를 참조하는 문서" 목록이 신뢰할 수 있고, related links 스코어링에서 backward 탐색이 올바르게 동작한다.

module backlink

sig Page {
  links: set Page,
  backlinks: set Page
}

-- backlink is the transpose of links
fact backlinkSymmetry {
  all a, b: Page | b in a.links iff a in b.backlinks
}

-- no self-backlinks unless self-links exist
assert noSpuriousBacklink {
  all p: Page | p in p.backlinks implies p in p.links
}

check noSpuriousBacklink for 6

alloy:model(backlink)

A→B, A→C, B→C 그래프에서 backlink 채우기

import { fillBacklinks } from './src/lib/wiki-builder.ts'
const m = new Map([
  ['A', { pagename: 'A', links: new Set(['B', 'C']), backlinks: new Set() }],
  ['B', { pagename: 'B', links: new Set(['C']), backlinks: new Set() }],
  ['C', { pagename: 'C', links: new Set(), backlinks: new Set() }],
])
fillBacklinks(m)
console.log(JSON.stringify({
  bBacklinks: [...m.get('B').backlinks],
  cBacklinks: [...m.get('C').backlinks].sort(),
}))

blResult={"bBacklinks":["A"],"cBacklinks":["A","B"]}

run:wiki

expr	expected
.bBacklinks	["A"]
.cBacklinks	["A","B"]

Most Wanted

링크는 걸려 있지만 아직 실질 내용이 없는 문서를 빈도순으로 정렬한다. 존재하지 않거나, 내용이 minChars 미만인 문서가 대상이다.

이 목록은 위키 편집자에게 "어떤 문서를 다음에 작성하면 좋을지" 안내하는 역할을 한다. 여러 문서에서 참조하는데 아직 비어 있는 문서가 가장 우선순위가 높다.

Missing(2회), Also(1회) 참조 — Exists는 내용 있으므로 제외

import { computeMostWanted } from './src/lib/wiki-builder.ts'
const metas = [
  { links: new Set(['Missing', 'Also', 'Missing']) },
  { links: new Set(['Missing', 'Exists']) },
]
const allMeta = new Map([['Exists', { md: 'x'.repeat(100) }]])
const result = computeMostWanted(metas, allMeta, 50, 10)
console.log(JSON.stringify(result))

$blResult={"bBacklinks":["A"],"cBacklinks":["A","B"]}

mwResult=[["Missing",2],["Also",1]]

run:wiki

expr	expected
.[0][0]	Missing
.[0][1]	2
.[1][0]	Also
.[1][1]	1

Substantial Page 필터링

본문 길이가 minChars 미만인 문서는 그래프에서 제외하고, 남은 문서의 링크도 실질 문서만 참조하도록 정리한다.

스텁 문서(제목만 있고 내용이 없는 문서)가 그래프에 포함되면 related links와 통계가 왜곡된다. 이 필터가 있어야 "실질적으로 읽을 가치가 있는 문서"만으로 그래프를 구축할 수 있다.

Big(100자), Small(1자), Other(200자) 중 50자 미만 제거 → Big, Other만 남음

import { pruneToSubstantialPages } from './src/lib/wiki-builder.ts'
const metas = [
  { pagename: 'Big', md: 'x'.repeat(100), links: new Set(['Small', 'Other']), backlinks: new Set() },
  { pagename: 'Small', md: 'x', links: new Set(['Big']), backlinks: new Set() },
  { pagename: 'Other', md: 'y'.repeat(200), links: new Set(), backlinks: new Set() },
]
const result = pruneToSubstantialPages(metas, 50)
console.log(JSON.stringify({
  pages: result.map(m => m.pagename),
  bigLinks: [...result[0].links],
}))

$blResult={"bBacklinks":["A"],"cBacklinks":["A","B"]}, $mwResult=[["Missing",2],["Also",1]]

pruneResult={"pages":["Big","Other"],"bigLinks":["Other"]}

run:wiki

expr	expected
.pages	["Big","Other"]
.bigLinks	["Other"]

Isolated Components

연결되지 않은 문서 그룹(고립 컴포넌트)을 탐지한다. 크기가 2 이상인 컴포넌트만 반환하며, 가장 많은 연결을 가진 문서가 대표 문서가 된다.

위키의 건강함은 문서들이 하나의 연결된 네트워크를 이루는 데 있다. 고립 컴포넌트가 존재한다는 것은 서로 관련 있는 문서들이 메인 그래프와 단절되어 발견되기 어렵다는 뜻이다. 이 탐지 결과를 편집자에게 보여주면 누락된 링크를 추가하도록 유도할 수 있다.

컴포넌트는 그래프의 분할이다: 모든 페이지는 정확히 하나의 컴포넌트에 속하고, 서로 다른 컴포넌트의 페이지 사이에는 링크가 없다.

module component

sig Page {
  links: set Page,
  backlinks: set Page
}

sig Component {
  members: set Page
}

-- 모든 페이지는 정확히 하나의 컴포넌트에 속함
fact partition {
  all p: Page | one c: Component | p in c.members
}

-- 컴포넌트 내 연결: 같은 컴포넌트의 페이지끼리만 링크
fact internalLinks {
  all c: Component | all p: c.members |
    p.links in c.members and p.backlinks in c.members
}

-- 컴포넌트 간 격리: 서로 다른 컴포넌트의 페이지 사이에 링크 없음
assert crossComponentIsolation {
  all disj c1, c2: Component |
    no p1: c1.members, p2: c2.members | p2 in p1.links
}

check crossComponentIsolation for 6

alloy:model(component)

{A→B}, {C→D} 두 개의 독립 컴포넌트 탐지

import { findIsolatedComponents } from './src/lib/graph.ts'
const m = new Map([
  ['A', { links: new Set(['B']), backlinks: new Set() }],
  ['B', { links: new Set(), backlinks: new Set(['A']) }],
  ['C', { links: new Set(['D']), backlinks: new Set() }],
  ['D', { links: new Set(), backlinks: new Set(['C']) }],
])
const comps = findIsolatedComponents(m)
console.log(JSON.stringify({
  count: comps.length,
  allSize2: comps.every(c => c.size === 2),
}))

$blResult={"bBacklinks":["A"],"cBacklinks":["A","B"]}, $mwResult=[["Missing",2],["Also",1]], $pruneResult={"pages":["Big","Other"],"bigLinks":["Other"]}

isoResult={"count":2,"allSize2":true}

run:wiki

expr	expected
.count	2
.allSize2	true