In [1]:

    

from directed_graph import DirectedGraph
from directed_graph import topk
import sys
import matplotlib.pyplot as plt

def Run_LTM(graph, seeds, rounds, centrality):
	v, e = graph.size()
	print("* running LTM({}) TOP {} {} - graph size: {} {}".format(rounds, len(seeds), centrality, v, e))
	influenced, kept, steps = graph.ltm(seeds, rounds)
	print("** influenced(%d) kept(%d) steps(%d)" % (len(influenced), len(kept), steps))
	return len(influenced), len(kept), steps


    

In [2]:

    

if __name__ == '__main__':
    
    rounds = 10
    seed = 100
    graph = DirectedGraph.from_filename('wiki-Vote.txt')
    nodes, edges = graph.size()

    print('# Edges = %d\tAverage Clustering = %f' % (graph.countEdges(), graph.toUndirect().average_clustering()))
    sys.stdout.flush()


    

    




# Edges = 103689	Average Clustering = 0.140898

In [3]:

    

print('# Eigenvector Centrality...')
    diffsum, cscores = graph.eigenvector_centrality()
    # print(diffsum)
    # print(cscores)
    top_eigenc = [a for a, b in topk(cscores, seed)]
    print(top_eigenc)
    print('# Done')
    sys.stdout.flush()


    

    




# Eigenvector Centrality...
[2565, 766, 1549, 1166, 2688, 457, 3352, 11, 1151, 1374, 2485, 3456, 2871, 2328, 5524, 737, 2237, 2398, 2651, 3453, 2972, 1133, 5079, 4310, 2576, 1608, 4037, 1305, 1297, 2145, 3447, 4712, 5189, 15, 4099, 789, 2297, 3026, 2658, 4967, 3449, 2326, 2790, 762, 813, 311, 2625, 825, 988, 2256, 2653, 3787, 2660, 3089, 5697, 2967, 2535, 4191, 722, 5802, 3614, 2713, 3642, 2066, 2693, 3568, 2654, 72, 2411, 4828, 3976, 68, 2135, 5022, 993, 5179, 3454, 3796, 996, 1972, 3615, 1496, 24, 3459, 3028, 5188, 5254, 3394, 5543, 4335, 1542, 5412, 4536, 1098, 122, 3641, 2323, 2240, 2859, 2700]
# Done

In [4]:

    

print('# Betweennes centrality...')
    bet, D = graph.betweennessEx()
    # print(bet)
    top_bet = [a for a, b in topk(bet, seed)]
    print(top_bet)
    print('# Done')
    sys.stdout.flush()


    

    




# Betweennes centrality...
[2565, 11, 457, 4037, 1549, 766, 1166, 15, 1374, 2237, 1151, 2688, 2328, 2470, 737, 1186, 5524, 72, 3352, 2625, 5079, 789, 2398, 2485, 5254, 1133, 2871, 2654, 214, 4191, 28, 1608, 6, 8293, 2972, 762, 600, 407, 665, 2658, 6774, 3456, 4310, 2535, 3453, 2651, 311, 5022, 2576, 1297, 5802, 173, 68, 2285, 24, 4828, 1098, 5189, 2256, 722, 3334, 4875, 36, 86, 3976, 6634, 7620, 5179, 3447, 4261, 1305, 306, 1542, 1026, 3642, 993, 5697, 4099, 5543, 996, 3028, 6327, 5800, 4967, 7553, 87, 4335, 7092, 3586, 1842, 4712, 3459, 988, 1717, 3089, 5210, 5484, 319, 310, 825]
# Done

In [5]:

    

print("# Lin's index...")
	lin = graph.lin_index(D)
	#print(lin)
	top_lin = [a for a, b in topk(lin, seed)]
	print(top_lin)
	print('# Done')
	sys.stdout.flush()


    

    




# Lin's index...
[2565, 766, 457, 1549, 1166, 1374, 11, 1151, 2688, 2485, 3352, 5524, 2328, 737, 1133, 3456, 2871, 68, 789, 1608, 15, 3453, 2651, 311, 4310, 72, 4037, 5079, 2237, 2972, 722, 2398, 2576, 3787, 2145, 600, 3447, 24, 5189, 1055, 1542, 36, 996, 173, 2658, 4712, 5697, 5802, 87, 1305, 825, 2240, 2535, 4099, 813, 2256, 1098, 2693, 1297, 762, 1496, 988, 2790, 2135, 5022, 3976, 2297, 2660, 784, 4828, 5254, 3026, 4967, 5179, 1210, 3642, 5543, 993, 2381, 3089, 2369, 3614, 3084, 3459, 3568, 3028, 3631, 3449, 1701, 4335, 3454, 127, 319, 4632, 407, 3334, 2323, 5002, 4191, 3641]
# Done

In [6]:

    

for _ in range(100):
        seed = 100
        max_lin_influenced, _, lin_rounds = Run_LTM(graph, top_lin[:seed], rounds, 'Lin')
        max_eigenc_influenced, _, eigenc_rounds = Run_LTM(graph, top_eigenc[:seed], rounds, 'Eigenvector')
        max_bet_influenced, _, bet_rounds = Run_LTM(graph, top_bet[:seed], rounds, 'Betweenness')
        lin_max_seed = seed
        eigenc_max_seed = seed
        bet_max_seed = seed

        while seed > 0 and max_lin_influenced < nodes:
            seed -= 5
            influenced_lin, _, _rounds = Run_LTM(graph, top_lin[:seed], rounds, 'Lin')
            if max_lin_influenced <= influenced_lin:
                max_lin_influenced = influenced_lin
                lin_max_seed = seed
                lin_rounds = _rounds
            else:
                break

        seed = 100
        while seed > 0 and max_eigenc_influenced < nodes:
            seed -= 5
            influenced_eigenc, _, _rounds = Run_LTM(graph, top_eigenc[:seed], rounds, 'Eigenvector')
            if max_eigenc_influenced <= influenced_eigenc:
                max_eigenc_influenced = influenced_eigenc
                eigenc_max_seed = seed
                eigenc_rounds = _rounds
            else:
                break

        seed = 100
        while seed > 0 and max_bet_influenced < nodes:
            seed -= 5
            influenced_bet, _, _rounds= Run_LTM(graph, top_bet[:seed], rounds, 'Betweenness')
            if max_bet_influenced <= influenced_bet:
                max_bet_influenced = influenced_bet
                bet_max_seed = seed
                bet_rounds = _rounds
            else:
                break


    

    




* running LTM(10) TOP 100 Lin - graph size: 7115 103689
** influenced(5795) kept(1320) steps(4)
* running LTM(10) TOP 100 Eigenvector - graph size: 7115 103689
** influenced(5772) kept(1343) steps(4)
* running LTM(10) TOP 100 Betweenness - graph size: 7115 103689
** influenced(5791) kept(1324) steps(3)
* running LTM(10) TOP 95 Lin - graph size: 7115 103689
** influenced(5812) kept(1303) steps(4)
* running LTM(10) TOP 90 Lin - graph size: 7115 103689
** influenced(5801) kept(1314) steps(4)
* running LTM(10) TOP 95 Eigenvector - graph size: 7115 103689
** influenced(5858) kept(1257) steps(4)
* running LTM(10) TOP 90 Eigenvector - graph size: 7115 103689
** influenced(5881) kept(1234) steps(4)
* running LTM(10) TOP 85 Eigenvector - graph size: 7115 103689
** influenced(5752) kept(1363) steps(3)
* running LTM(10) TOP 95 Betweenness - graph size: 7115 103689
** influenced(5797) kept(1318) steps(4)
* running LTM(10) TOP 90 Betweenness - graph size: 7115 103689
** influenced(5804) kept(1311) steps(4)
* running LTM(10) TOP 85 Betweenness - graph size: 7115 103689
** influenced(5722) kept(1393) steps(3)

In [7]:

    

print("Lin's Index: influenced={} seeds={} rounds={}".format(max_lin_influenced,lin_max_seed,lin_rounds))
print("BC: influenced={} seeds={} rounds={}".format(max_bet_influenced,bet_max_seed,bet_rounds))
print("E: influenced={} seeds={} rounds={}".format(max_eigenc_influenced,eigenc_max_seed,eigenc_rounds))


    

    




Lin's Index: influenced=5812 seeds=95 rounds=4
BC: influenced=5804 seeds=90 rounds=4
E: influenced=5881 seeds=90 rounds=4

In [8]:

    

%matplotlib inline


    

In [9]:

    

fig, ax = plt.subplots()

    bar_width = 0.35

    opacity = 0.4

    rects1 = plt.bar(1, max_lin_influenced, width=bar_width, alpha=opacity, color='b', label='Lin')

    rects2 = plt.bar(2, max_eigenc_influenced, width=bar_width, alpha=opacity, color='r', label='Eigenvector')

    rects3 = plt.bar(3, max_bet_influenced, width=bar_width, alpha=opacity, color='y', label='Betweenness')

    plt.xlabel('Centrality Measures')
    plt.ylabel('Influenced')
    plt.title('Influenced Comparison')
    plt.xticks([1.2,2.2,3.2], ('L', 'E', 'B'))

    plt.legend(bbox_to_anchor=(1.05, 1), loc=2, borderaxespad=0.)

    plt.tight_layout()

    plt.savefig('wikivote.png')
    plt.show()


    

In [ ]:

    




    

In [ ]: