I’ve been working at the Wolfram Summer Research Program as a TA for the past week, and it’s been a total adventure. I was running a social activity for the students, specifically the Wiki Game, where you have to get from a certain Wikipedia page to another page using only the links in the articles. As the students were playing, another TA suggested that we create an algorithm to get from the start to the end Wikipedia page, and I decided that this was a fantastic use of my time.
Function
Function
So here’s the function! Essentially, it takes the title of the starting Wikipedia page and the ending Wikipedia page, and first creates a 3-level deep list of all the links forward from the starting page and backward from the ending page. For example, if the starting page is “The Bible” and the ending page is “Graph theory”, here are the first 20 links forward and the first 20 links backward:
In[]:=
WikipediaData["The Bible","LinksRules","MaxLevelItems"->20,"MaxLevel"->3][[1;;20]]
Out[]=
{Bible1890 Manifesto,Bible1 Enoch,Bible1 Esdras,Bible1 Maccabees,Bible2 Baruch,Bible2 Esdras,Bible2 John,Bible2 Maccabees,Bible2 Peter,Bible3 Enoch,Bible3 John,Bible3 Maccabees,Bible4 Maccabees,Bible613 commandments,BibleAaron ben Moses ben Asher,BibleAbaddon,BibleAbijah,BibleAbilene (biblical),BibleAblution in Christianity,BibleAbner}
In[]:=
WikipediaData["Graph theory","LinksRules","MaxLevelItems"->20,"MaxLevel"->3][[1;;20]]
Out[]=
{Graph theoryACM Computing Classification System,Graph theoryAbstract algebra,Graph theoryAbstract simplicial complex,Graph theoryAcademic Press,Graph theoryAdjacency list,Graph theoryAdjacency matrix,Graph theoryAlexandre-Théophile Vandermonde,Graph theoryAlfred Kempe,Graph theoryAlfréd Rényi,Graph theoryAlgebra,Graph theoryAlgebraic geometry,Graph theoryAlgebraic graph theory,Graph theoryAlgebraic number theory,Graph theoryAlgebraic topology,Graph theoryAlgorithm,Graph theoryAlgorithm design,Graph theoryAlgorithmic efficiency,Graph theoryAnalysis of algorithms,Graph theoryAnalytic geometry,Graph theoryAnalytic number theory}
Then it generates an undirected graph which combines these lists of rules:
In[]:=
Graph[(WikipediaData["The Bible","LinksRules","MaxLevelItems"->20,"MaxLevel"->3])~Join~(WikipediaData["Graph theory","LinksRules","MaxLevelItems"->20,"MaxLevel"->3]),VertexLabels->Placed["Name",Tooltip]]//DirectedGraph
Out[]=
Graph
This graph is too big to show directly, but by lowering the max levels, you can see what the graph looks like. Here’s the graph connecting “Graph theory” and “Computer science” that goes 3 levels forward and 2 levels backward.
In[]:=
Graph[(WikipediaData["Graph theory","LinksRules","MaxLevelItems"->20,"MaxLevel"->3])~Join~(WikipediaData["Computer science","LinksRules","MaxLevelItems"->20,"MaxLevel"->2]),VertexLabels->Placed["Name",Tooltip]]//DirectedGraph
Out[]=
And then it just finds the shortest path between the starting and ending node, with the function FindShortestPath. Continuing with our example, the shortest path between “Computer science” and “Graph theory” is:
In[]:=
FindShortestPath[(Graph[(WikipediaData["Graph theory","LinksRules","MaxLevelItems"->20,"MaxLevel"->3])~Join~(WikipediaData["Computer science","LinksRules","MaxLevelItems"->20,"MaxLevel"->2]),VertexLabels->Placed["Name",Tooltip]]//DirectedGraph),"Computer science","Graph theory"]
Out[]=
{Computer science,ACM Computing Classification System,Computational complexity theory,Adjacency list,Graph theory}
We can highlight this path to visualize the connection between these two nodes.
In[]:=
HighlightGraph[(Graph[(WikipediaData["Graph theory","LinksRules","MaxLevelItems"->20,"MaxLevel"->3])~Join~(WikipediaData["Computer science","LinksRules","MaxLevelItems"->20,"MaxLevel"->2]),VertexLabels->Placed["Name",Tooltip]]//DirectedGraph),PathGraph[FindShortestPath[(Graph[(WikipediaData["Graph theory","LinksRules","MaxLevelItems"->20,"MaxLevel"->3])~Join~(WikipediaData["Computer science","LinksRules","MaxLevelItems"->20,"MaxLevel"->2]),VertexLabels->Placed["Name",Tooltip]]//DirectedGraph),"Computer science","Graph theory"]]]
Out[]=
So that’s our code! I put it into a function wikialgorithm, as shown below. However, a few notes to remember:
◼
You can change the max levels of the algorithm, so if the function is returning an error because there’s too much data or if it can’t find a path because there’s too little data, you can change the max levels to find the best path. (3, 2) seems to be the sweet spot.
◼
The max levels my computer could handle is 3 in each direction (so 3,3), which means the longest chain that could be identified by this function on my computer is 6 clicks long. Most chains in Wikipedia are 6 clicks or less, but there are a few chains that are 7 or 8 clicks.
◼
If the graph/data is too big, the algorithm can’t run FindShortestPath and returns an error, so if that occurs then you may be searching through too much. If anyone knows how to fix that, feel free!
◼
Make sure the strings you input are the titles of the Wikipedia pages!
In[]:=
wikialgorithm[start_String,end_String,lvl1_Integer,lvl2_Integer]:=Module[{flinks=WikipediaData[start,"LinksRules","MaxLevelItems"->20,"MaxLevel"->lvl1],blinks=WikipediaData[end,"BacklinksRules","MaxLevelItems"->20,"MaxLevel"->lvl2]},g=Graph[flinks~Join~blinks,VertexLabels->Placed["Name",Tooltip]]//DirectedGraph;If[Length[FindShortestPath[g,start,end]]!=0,Print[FindShortestPath[g,start,end]];HighlightGraph[g,PathGraph[FindShortestPath[g,start,end]],EdgeStyle->{Red,Thick}],Print["No match present!"]]]
Examples
Examples
And now, for a few examples:
In[]:=
wikialgorithm["Bible","Graph theory",3,2]
{Bible,1890 Manifesto,Baptism for the dead,Albert Einstein,Charles Sanders Peirce,Graph theory}
Out[]=
In[]:=
wikialgorithm["Pokémon Go","Surfing",3,2]
{Pokémon Go,4Kids Entertainment,American Film Institute,California,Surfing}
Out[]=
In[]:=
wikialgorithm["Benford's law","Agriculture",1,2]
No match present!
If we expand the maximum levels, we find a path:
Future Work
Future Work
This was pretty fun to make, even though it drained my computer battery in seconds. As for future work, there’s probably a better way to find the shortest path beyond brute force, so it’d be cool to study that. Kegan suggested using machine learning for this, so there’s a potential option.
Thanks to the other TAs for inspiring me to do this project, and to Kegan and Sophie for listening to my Wikipedia rants :)
Note: After testing with other TAs, we’ve realized that WikiData uses a third party API of Wikipedia and as such isn’t updated to the most recent version. It says that there are certain links between pages (such as Age of Enlightenment to ABCANZ Armies) which do not currently exist. Thanks to Logan and Theo who helped me figure out the problem! Use this at your own peril :)
CITE THIS NOTEBOOK
CITE THIS NOTEBOOK
WikiGame: minimum steps from one article to another using internal links
by Samikshaa Natarajan
Wolfram Community, STAFF PICKS, July 8, 2023
https://community.wolfram.com/groups/-/m/t/2954339
by Samikshaa Natarajan
Wolfram Community, STAFF PICKS, July 8, 2023
https://community.wolfram.com/groups/-/m/t/2954339