Smart Social Network Discovery using the POMDP framework.
A report describing this project is located in doc/report.pdf.
The ipython notebooks in notebooks contain basic usage examples.
This code was designed to be used with the POMDPs.jl framework. Unfortunately changes to this framework will probably make this code incompatible, so it will have to be updated to be used in the future. If you would like to resurrect this code and start using it, please contact me at zsunberg(at)stanford.edu.
The MCTS solver used for this is implemented in POMCP.jl.
julia> Pkg.clone("https://github.com/sisl/NetworkDiscovery.jl")
-
CommunityNetworkrepresents a social network with each vertex affiliated with a community, aCommunityNetworkobject functions as the state of the POMDP. -
CommunityAffiliationPOMDPdescribes an entire problem, with the probing budget, statistical information for generating the network, etc. -
ProbeNodeandGuessAffiliationare the types that represent actions. TheNeighborhoodtype represents the observation.
RevealedGraphholds all the edges and nodes revealed by probing. This structure is used by both the heuristic policy and the MCTS policy.
-
DiscoveryHeuristicsimply holds a probing policy and an affiliation-guessing policy. On steps 1 through T (see the report), it uses theprobingpolicy to decide which vertex to probe; on step T+1, it uses theguesspolicy to guess the target node affiliation. -
ProbeHighestDegreeprobes the node with the highest revealed degree (see report) -
GuessBasedOnNeighborsguesses the target node affiliation as described in the report.