tl_growth_sim.py

"""
memory efficient simulation of network growth
pypy is ~10 times faster
"""
import math
import time
import array
import random
import profile


# num users
max_uid = 1000 * 1000**2
num_seed_users = 1000

# dunbar's number * mobile phone and data factor * trust_factor
friends_per_user = int(150 * 0.4 * 0.5 / 2) * 2

assert friends_per_user % 2 == 0
P_connect_base = 1.
kad_base = 3
kad_base = int(max_uid ** (1. / (friends_per_user / 2)))


# model, that the more tls one has the more likely it is to add new connections

# trustlines stored as friends idx via bits
trustlines = array.array('i')
item_size = trustlines.itemsize
print "item_size", item_size
print "creating storage", max_uid * item_size / 1024**2, "MB"
assert friends_per_user <= item_size * 8
trustlines.extend(0 for i in xrange(max_uid))
print "done"


def testBit(int_type, offset):
    mask = 1 << offset
    return(int_type & mask)


def setBit(int_type, offset):
    # assert offset < item_size * 8  # based on array datatype
    mask = 1 << offset
    return(int_type | mask)


def clearBit(int_type, offset):
    mask = ~(1 << offset)
    return(int_type & mask)


def getBits(int_type):
    i = 0
    while int_type >= 1 << i:
        if testBit(int_type, i):
            yield i
        i += 1


########### FOF graph ##########################


def friend(uid, idx):
    "use kademlia style topography to model network of users"
    assert idx < friends_per_user
    if idx < friends_per_user / 2:
        # forward connexting
        distance = kad_base**idx
        assert distance < max_uid / 2
        return (uid + distance) % max_uid
    else:
        # backward connecting
        idx -= friends_per_user / 2
        assert idx >= 0
        distance = kad_base**idx
        assert distance < max_uid / 2
        return (max_uid + uid - distance) % max_uid


def friend_index(uid, fid):
    for idx in range(friends_per_user):
        if friend(uid, idx) == fid:
            return idx
    raise Exception


##############################################

def P_accept_connection(uid, P_base=1.):
    "humans are different, some are more open to new tech, others more hestitant"
    personality = uid % friends_per_user  # global characteristic per user
    decay_factor = 1.1
    return P_base / decay_factor**personality


def can_onboard(uid, rnd, P_base=1.):
    "odds of convincing a peer to join depend on personality"
    assert 0 < rnd < 1
    return bool(rnd < P_accept_connection(uid, P_base))


def P_trigger_connection(num_friends, P_base=1.):
    "the more connections one has, the more he interacts with the tool"
    decay_factor = 1.1
    return P_base / decay_factor ** (friends_per_user - num_friends)


def tries_connect(uid, rnd, P_base=1.):
    num_friends = sum(getBits(trustlines[uid]))
    return bool(rnd < P_trigger_connection(num_friends, P_base))


def select_friend_to_connect(uid, rnd):
    # assert 0 < rnd < 1
    # _ = friends(uid)
    # f = _[int(rnd * len(_))]
    # return f
    idx = int(rnd * friends_per_user)
    return friend(uid, idx)


def connect_users(A, B):
    for uid, fid in ((A, B), (B, A)):
        idx = friend_index(uid, fid)
        v = trustlines[uid]
        if testBit(v, idx):
            return False
        trustlines[uid] = setBit(v, idx)
    return True


num_trustlines = 0
num_users = num_seed_users


def period(i):
    global num_users, num_trustlines
    for uid, peers in enumerate(trustlines):
        if not peers:
            continue
        if not tries_connect(uid, random.random(), P_base=1.):
            continue
        fid = select_friend_to_connect(uid, random.random())
        if not (trustlines[fid] or
                can_onboard(fid, random.random(), P_base=1)):
            continue
        new_user = bool(trustlines[fid] == 0)
        success = connect_users(uid, fid)
        if success:
            if new_user:
                num_users += 1
            num_trustlines += 1
    print "{}\t{}\t{}".format(i, num_users, num_trustlines)


def run(periods=20):
    print "max_uid", max_uid
    print "friends_per_user", friends_per_user
    print "kad_base", kad_base

    print "adoption probability (per approach) distribution"
    print list("{:.2f}".format(P_accept_connection(i)) for i in range(friends_per_user))
    print "connection init probability (per approach) by number of connections"
    print list("{:.2f}".format(P_trigger_connection(i)) for i in range(1, friends_per_user + 1))

    for i in range(num_seed_users):
        idx = int(random.random() * max_uid)
        trustlines[idx] = 1  # set initial user
    for i in range(periods):
        st = time.time()
        period(i)
        elapsed = time.time() - st
        # print elapsed, elapsed / num_users


if __name__ == '__main__':
    if True:
        run(1000)
    else:
        profile.run("run()", "profile_stats_0.stats")
        import pstats
        stats = pstats.Stats('profile_stats_0.stats')
        # Clean up filenames for the report
        stats.strip_dirs()
        # Sort the statistics by the cumulative time spent in the function
        stats.sort_stats('cumulative')
        stats.print_stats()


def test_bits():
    ########## TEST BITS #########
    v = 0
    bits = (0, 1, 3, 4, 7)
    for bit in bits:
        v = setBit(v, bit)
        v = setBit(v, bit)  # set twice
        assert testBit(v, bit)
        assert bit in getBits(v)

    assert v == sum(2**i for i in bits)

    assert bits == tuple(getBits(v))
    for bit in bits:
        v = clearBit(v, bit)
        v = clearBit(v, bit)  # clear twice
        assert not testBit(v, bit)
        assert bit not in getBits(v)
    assert not tuple(getBits(v))
    assert v == 0


def test_graph():

    ######## test FoF graph ######################
    for uid in range(max_uid):
        print friends(uid)
        for i, fid in enumerate(friends(uid)):
            assert uid in friends(fid)
            assert i == friend_index(uid, fid), (i, friend_index(uid, fid))