Original CPP Code: https://ameo.link/u/bin/2f9 graph.h: https://ameo.link/u/bin/2fb =====Traversal Algorithms===== 1. BFS: Simple Breadth-first Search Well-known and commonly used algorithm **** Not going to write psuedocode because it def. already exists in Python 2. Coupon Collector Equation https://en.wikipedia.org/wiki/Coupon_collector%27s_problem How many tries will it take to collect all coupons in an urn given that each coupon is replaced after being found? **** Psuedocode: https://ameo.link/u/bin/2fh 3. Max Degree Connected Dual Fitting Retrieves nodes with largest unconvered degree first (uncovered degree = degree - edges that were already sampled) **** Not writing psuedocode because it's rather self-explanetory. Start with node with highest degree Find node with greatest uncovered degree and pick repeat until all nodes discovered or budget exhausted 4. Frontier Sampling RW also counting neighbors **** Psudeocode: https://ameo.link/u/bin/2fe 5. DFS Depth-first Search One starts at the root (selecting some arbitrary node as the root in the case of a graph) and explores as far as possible along each branch before backtracking. **** I'm not going to create psuedocode for this as it's a well-known algorithm and probably already exists in Python +6. GSI Generalized SI sampling **** Psuedocode: https://ameo.link/u/bin/2fg Results: https://ameo.link/u/bin/2fz 7. Random Walk Neign Dumbbell RW also counting neighbors **** Psuedocode: https://ameo.link/u/bin/2ff // DISCLAIMER: I really don't know what's going on in this one. 8. Edge Sampling Neig Edge sampling also counting neighbors **** Psuedocode: https://ameo.link/u/bin/2fd 9. Edge Sampling Neig Two Nodes Edge sampling where both end nodes are sampled **** Psuedocode: https://ameo.link/u/bin/2fa 10. Max Degree Retrieves nodes with largest degree first **** Simple max degree algorithm; not writing psuedocode. Makes a list of all nodes and sorts by degree Picks nodes in order; **NOT A WALK** +11. Max Sampled Degree CONNECTED: Retrieves nodes with largest edges sampled first **** Psuedocode: https://ameo.link/u/bin/2fk Results: https://ameo.link/u/bin/2fs 12. LP Retrieves nodes with largest degree first **** Looks like a dynamic or interactive version of Max Degree 13. Random Walk Neign **** Psuedocode: https://ameo.link/u/bin/2fc Random walk also counting neighbors Maximum Expected d-Excess Degree (MEED): - Useful for traversing networks with unknown topologies (discovered as they're traversed) 1. Start tree T = {v} 2. Select neighbors of T with max EXPECTED excess degree 3. Add node to T 4. GOTO 2 until budget exhausted Maximum Observable Degree (MOD): - Simplicifaction of MEED for random power law networks 1. Select unrecruited w/ max recruited neighbors 2. Invite node 3. GOTO 1 until budget is exhausted =====GENERAL NOTES===== - They do work comparing the performance of several existing network analysis algorithms, many of which already exist in Python and don't need to be re-written. - BFS is performs worse than greedy algorithms that select the nodes with the highest visible degree - Random walk without replacement also outperforms BFS - for some important families of random networks, the node with maximum observed degree is also the node with the maximum expected excess degree (p19) - Summary DFS consistently bad BFS suffers with clustering RW better than BFS MOD better overall - It seems that they have different sub-algos for selecting the initial node to create the tree - the SNAP network analysis library (which is used extensively by the C++ script) has a Python version: https://snap.stanford.edu/snappy/doc/ =====C++ TRANSCRIPTION NOTES===== - I really don't get how the C++ typedef system works - Not sure what <stuff> operator does; think it's related to vectors but not sure.