文件列表:

IC (0, 2018-03-15)
IC\ArbitraryP (0, 2018-03-15)
IC\ArbitraryP\CCWP.py (14030, 2015-05-19)
IC\ArbitraryP\DD.py (6006, 2015-05-19)
IC\ArbitraryP\Graphs.py (3983, 2015-05-19)
IC\ArbitraryP\Harvester.py (5154, 2015-05-19)
IC\ArbitraryP\LP.m (904, 2015-05-19)
IC\ArbitraryP\MPST.py (54607, 2015-05-19)
IC\ArbitraryP\Models.py (1323, 2015-05-19)
IC\ArbitraryP\PMIA.py (11192, 2015-05-19)
IC\ArbitraryP\PossibleWorlds.py (9796, 2015-05-19)
IC\ArbitraryP\calculateSpread.py (1875, 2015-05-19)
IC\ArbitraryP\random_heuristic.py (2764, 2015-05-19)
IC\ArbitraryP\reverseCCWP.py (12678, 2015-05-19)
IC\ArbitraryP\reverseCCWPforIAC.py (8534, 2015-05-19)
IC\ArbitraryP\reverseDD.py (5155, 2015-05-19)
IC\ArbitraryP\reverseDegree.py (4204, 2015-05-19)
IC\ArbitraryP\reversePMIA.py (11312, 2015-05-19)
IC\ArbitraryP\reverseRDM.py (4129, 2015-05-19)
IC\ArbitraryP\runCascade.py (1935, 2015-05-19)
IC\ArbitraryP\runIAC.py (10146, 2015-05-19)
IC\ArbitraryP\script.py (11949, 2015-05-19)
IC\ArbitraryP\visualisation.py (25434, 2015-05-19)
IC\CCHeuristic.py (2889, 2015-05-19)
IC\CCparallel.py (2298, 2015-05-19)
IC\IC.py (2452, 2015-05-19)
IC\SCCHeuristic.py (2751, 2015-05-19)
IC\__init__.py (23, 2015-05-19)
IC\binaryDegreeDiscount.py (2978, 2015-05-19)
IC\bruteforce.py (1584, 2015-05-19)
IC\continiousSearch.py (3793, 2015-05-19)
IC\degreeDiscount.py (3189, 2015-05-19)
IC\degreeDiscountIC.txt (247, 2015-05-19)
IC\degreeHeuristic.py (1459, 2015-05-19)
IC\generalGreedy.py (1275, 2015-05-19)
IC\generateGraph.py (701, 2015-05-19)
IC\lemma1.py (1727, 2015-05-19)
... ...

Influence maximization in Social Graphs ======================================= Repository for research project that studies [influence maximization problem.](http://www-bcf.usc.edu/~dkempe/publications/spread.pdf) Degree Discount Algorithm ------------------------- Degree discount heuristic was proposed first by [Chen et al.](http://snap.stanford.edu/class/cs224w-readings/chen09influence.pdf) (Algorithm 4) Its results are slightly inferior than greedy hill-climbing algorithms, however it runs several orders of magnitudes faster. It's fine-tuned for Independent Cascade model. Running time is O(k*log(n)+m), where k - number of initial targets, n - number of vertices, m - number of edges. Representative Nodes Algorithm ------------------------------ Representative nodes heuristic is searching for the set of k nodes such that its size is maximum. Two different definitions of set size are used. First is cumulative sum of all distances between each pair of vertices inside the set. Second is minimum distance between a pair of vertices in the set. Algorithm didn't show significant results, probably because small differences in edge weights don't make some vertices be "more influential" than others. General Greedy Algorithm ------------------------ General greedy heuristic is iterative method, each step it chooses node that along with already chosen nodes will bring the most propagation. Since propagation is random process for each node it runs R iteration of RanCas to calculate the average number of nodes it reaches. Running time is O(knRm). Source: [Chen et al.](http://snap.stanford.edu/class/cs224w-readings/chen09influence.pdf) (Algorithm 1) New Greedy IC Algorithm ----------------------- newGreedyIC heuristic reduces the amount of iterations in general greedy algorithm. Running time is O(kRm). Source: [Chen et al.](http://snap.stanford.edu/class/cs224w-readings/chen09influence.pdf) (Algorithm 2) Single Discount --------------- A simple degree discount heuristic where each neighbor of a newly selected seed discounts its degree by one. This can be applied to all influence cascade models. The heuristic has the same running time as for degree discount heuristic. Additional information can be found in [Chen et al.](http://snap.stanford.edu/class/cs224w-readings/chen09influence.pdf) Degree Heuristic ---------------- As a comparison, a simple heuristic that selects the k vertices with the largest degrees. Running time is O(m). Additional information can be found in [Kempe et al.](http://www-bcf.usc.edu/~dkempe/publications/spread.pdf) and [Chen et al.](http://snap.stanford.edu/class/cs224w-readings/chen09influence.pdf) Random Heuristic ---------------- As a baseline, heuristic takes k nodes uniformly at random. Running time is O(k).

近期下载者：

相关文件：

评论：[我要评论] [举报此文件]

收藏者：