双曲几何

Wang Cheng-Jun edited this page Dec 19, 2016 · 1 revision

计算传播学是计算社会科学的重要分支。它主要关注人类传播行为的可计算性基础,以传播网络分析、传播文本挖掘、数据科学等为主要分析工具,(以非介入地方式)大规模地收集并分析人类传播行为数据,挖掘人类传播行为背后的模式和法则,分析模式背后的生成机制与基本原理,可以被广泛地应用于数据新闻和计算广告等场景,注重编程训练、数学建模、可计算思维。

Clone this wiki locally

Table of Contents

随机几何图模型

缩略图

 Penrose, Mathew, Random Geometric Graphs, Oxford Studies in Probability, 5, 2003. The random geometric graph model places n nodes uniformly at random in the unit cube  Two nodes `u,v` are connected with an edge if `d(u,v)<=r` where `d` is the Euclidean distance and `r` is a radius threshold.
def random_geometric_graph(n, radius, dim=2, pos=None):
    G=nx.Graph()
    G.name="Random Geometric Graph"
    G.add_nodes_from(range(n)) 
    if pos is None:
        # random positions 
        for n in G:
            G.node[n]['pos']=[random.random() for i in range(0,dim)]
    else:
        nx.set_node_attributes(G,'pos',pos)
    # connect nodes within "radius" of each other
    # n^2 algorithm, could use a k-d tree implementation
    nodes = G.nodes(data=True)
    while nodes:
        u,du = nodes.pop() 
        # u is nodeId, 
        # du is the pos_dict with 'pos' as the key
        pu = du['pos'] # pu is the pos list of the nodeId
        for v,dv in nodes:
            pv = dv['pos']
            d = sum(((a-b)**2 for a,b in zip(pu,pv)))
            if d <= radius**2:
                G.add_edge(u,v)
    return G
 Jiang Zhang, Xintong Li, Xinran Wang, Wen-Xu Wang, and Lingfei Wu. Scaling behaviours in the growth of networked systems and their geometric origins. Scientific Reports, 5:9767 EP –, 04 2015. 在几何图模型当中,存在一个d维的欧氏空间。初始状态,在这个网络的中心有一个种子节点存在。每一个时间步t有一个新节点p生成,但仅仅当p在已经存在的节点q的r距离范围以内,p才能被加入网络,并在p和所有与之在r范围内的节点q之间建立链接。
# Jiang Zhang, Xintong Li, Xinran Wang, Wen-Xu Wang, and Lingfei Wu. 
Scaling behaviours in the growth of networked systems and their geometric origins. Scientific Reports, 5:9767 EP –, 04 2015.

def spatial_constrained_model(l,r,n):
    #l=100.0;r=3;n=10000
    loc={}
    loc[0]=(l/2.0,l/2.0)
    G=nx.Graph()
    G.add_node(0)
    for i in range(1,n+1):
        xi,yi=random.random()*l,random.random()*l
        neighbors=[]
        for j in loc:
            xj,yj=loc[j]
            if np.sqrt((xi-xj)**2+(yi-yj)**2)<r:
                neighbors.append(j)
                G.add_edge(i,j)
        if neighbors:
            loc[i]=(xi,yi)
    return loc,G

def plotm(loc,G,ax,col):
    for i,j in G.edges():
        xi,yi=loc[i]
        xj,yj=loc[j]
        plt.plot([xi,xj],[yi,yj],'b-',alpha=0.5)
    for i in loc:
        xi,yi=loc[i]
        plt.plot(xi,yi,marker='.',linestyle=,
                 color=col,markersize=2,alpha=0.5)
    plt.legend(loc=1,numpoints=1,fontsize=10)
    plt.xlim(0,100)
    plt.ylim(0,100)

Hyperbolic Geometry

重点阅读论文,分析的数据、使用的方法

  1. Popularity versus similarity in growing networks http://www.nature.com/nature/journal/v489/n7417/full/nature11459.html paper http://www.nature.com/nature/journal/v489/n7417/extref/nature11459-s1.pdf 附件]https://www.cut.ac.cy/digitalAssets/virtualPath/116/116730_popsim_data.zip Datahttp://www.nature.com/nature/journal/v489/n7417/extref/nature11459-s1.pdf 附件]https://www.cut.ac.cy/digitalAssets/virtualPath/116/116730_popsim_data.zip Data
  2. Sustaining the Internet with Hyperbolic Mapping http://dx.doi.org/10.1038/ncomms1063 paper http://www.nature.com/ncomms/journal/v1/n6/full/ncomms1063.html#/supplementary-information data
  3. Hyperbolic geometry of complex networks[J]. Physical Review E, 2010, 82(3): 036106. Krioukov D, Papadopoulos F, Kitsak M, et al.
  4. D. Krioukov, Clustering Implies Geometry in Networks, Physical Review Letters, v.116, 208302, 2016
缩略图

Notes

 isotropic 1. invariant with respect to direction 各向同性

1. Euclidean (flat); 2. spherical (positively curved); 3. hyperbolic (negatively curved).

Fragkiskos Papadopoulos

Fragkiskos Papadopoulos

 Fragkiskos Papadopoulos is an Assistant Professor of the Department of Electrical Engineering, Computer Engineering and Informatics at Cyprus University of Technology. He was previously a (tenure-track) Lecturer at the same department (2011-2015), and a visiting Lecturer at the Dept. of Electrical and Computer Engineering at the University of Cyprus (2009-2010). He received the Diploma in Electrical and Computer Engineering from the National Technical University of Athens (NTUA) in 2002. In 2004 and 2007 he received respectively the MSc and PhD degrees in Electrical Engineering from the University of Southern California (USC), Los Angeles. During 2008-2009 he was a postdoctoral researcher at the Center for Applied Internet Data Analysis (CAIDA) at the University of California, San Diego (UCSD). His research interests are in network science, complex networks, network theory, data analysis, and computer networking. His research has been published in major peer reviewed international scientific journals, including Nature, Nature Physics and Nature Communications. 

http://www.cut.ac.cy/eecei/staff/f.papadopoulos/?languageId=2

Dima Krioukov

缩略图

http://www.northeastern.edu/dima/pub/ DK-LAB: http://www.dk-lab.net/

From Network geometry inference using common neighbors. Fragkiskos Papadopoulos, Rodrigo Aldecoa, and Dmitri Krioukov. Phys. Rev. E 92, 022807 – Published 12 August 2015

 We introduce and explore a method for inferring hidden geometric coordinates of nodes in complex networks based on the number of common neighbors between the nodes. We compare this approach to the HyperMap method, which is based only on the connections (and disconnections) between the nodes, i.e., on the links that the nodes have (or do not have). We find that for high degree nodes, the common-neighbors approach yields a more accurate inference than the link-based method, unless heuristic periodic adjustments (or “correction steps”) are used in the latter.

Marian Boguna

Marian Boguna

http://complex.ffn.ub.es/~mbogunya/index.php

 He is an associate professor and Icrea Academia researcher at the Departament de Física Fonamental, Universitat de Barcelona. Spain.  Currently,  His main research interests focus on Complex Systems and Complex Networks, two exciting and multidisciplinary fields of research that apply Statistical Physics techniques to the understanding of the many networked systems around us.

视频

Universal Hyperbolic Geometry (UHG) https://www.youtube.com/playlist?list=PL6ACFCC19EA82CA71

软件

生成双曲几何图

Hyperbolic-Graph-Generator: A set of tools to generate synthetic graphs embedded into a hyperbolic space and to test the greedy routing. https://github.com/named-data/Hyperbolic-Graph-Generator

计算双曲几何

snappy: SnapPy is a program for studying the topology and geometry of 3-manifolds, with a focus on hyperbolic structures. https://pypi.python.org/pypi/snappy/2.3.2

三维双曲空间可视化

pyh3 https://github.com/buzzfeed/pyh3 a scalable, high performance and interactive graph visualization in 3D hyperbolic space

自己写一个HyperMaping

200px

  1. Hypermap C++ Code: https://bitbucket.org/dk-lab/2015_code_hypermap, Code from the paper "Network Geometry Inference using Common Neighbors", F. Papadopoulos, R. Aldecoa, and D. Krioukov, Physical Review E, Vol. 92, Issue 2, August 2015, implementing the HyperMap-CN Embedding Method.
  2. HyperMap Embedding Code: http://www.cut.ac.cy/digitalAssets/virtualPath/116/116986_HyperMap_EPSO.zip, Code from the paper "Network Mapping by Replaying Hyperbolic Growth", F. Papadopoulos, C. Psomas, and D. Krioukov, IEEE/ACM Transactions on Networking, Vol. 23, No. 1, February 2015, implementing the HyperMap Embedding Method and the E-PSO Model.
MCMC method, including the Metropolis-Hastings sampler https://people.duke.edu/~ccc14/sta-663/MCMC.html

HyperMap

  1. Hypermap C++ Code: https://bitbucket.org/dk-lab/2015_code_hypermap
  2. HyperMap Embedding Code: http://www.cut.ac.cy/digitalAssets/virtualPath/116/116986_HyperMap_EPSO.zip
Hypermap C++ Code用法:
tar -xvzf HyperMap-v1.tar.gz
cd HyperMap-v1

To compile, use:

make

To run:

./hypermap -i graph.txt -g gamma -t temperature

- graph.txt: File containing the network to embed. Each line must be of the form

    id_1 id_2

    if node with id_1 is connected with node with id_2. Links are assumed
    bidirectional, so that if id_1 id_2 is present in graph.txt then id_2 id_1
    should not be present (see for example the AS topologies under the
    AS_topologies folder.)

- gamma: Value of the exponent of the power-law degree distribution

- temperature: Temperature of the network to embed (see paper).

Optional command line parameters:

 - '-z zeta': Curvature of the hyperbolic space (default: 1).
 
 - '-k k_speedup': The speedup heuristic is run for all nodes with degree k &lt; k_speedup (default: 0, i.e., the speedup heuristic is not run by default, see paper).
 
 - '-m m_in': Expected initial node degree (default: 1, see paper).
 
 - '-L L_in': Internal link rate (default: L = (kbar-2*m)/2, where kbar is the average node degree in the input graph, see paper).

 - '-o outFile': Name for the output file that will contain the inferred node coordinates (default: coordinates_embedding.txt).

 - '-c no': Deactivate the correction steps detailed in the paper.
 
 
The output of the program is the file coordinates_embedding.txt, which contains
the inferred angular and radial coordinates of each node in graph.txt. Each
line is of the form

  id angular_coordinate radial_coordinate

在该repo的目录下,有

ARK200909_gcc.net
ARK200912_gcc.net
ARK201003_gcc.net
ARK201006_gcc.net
ARK201009_gcc.net
ARK201012_gcc.net
coordinates_embedding_ARK200909.txt
coordinates_embedding_ARK200912.txt
coordinates_embedding_ARK201003.txt
coordinates_embedding_ARK201006.txt
coordinates_embedding_ARK201009.txt
coordinates_embedding_ARK201012.txt
作为测试数据

运行

./hypermap -i ../../popsim_data/INTERNET/ARKbyBGP_2009_6.txt -g 2.1 -t 0.69

速度很慢,计算约20分钟后,得到了前五行结果:

1 3356 3.1415927 1.8312584
2 174 3.06 3.091526
3 3549 3.24 3.8287353
4 7018 4.04 4.3517936
5 701 4.03 4.7575092

与相应的coordinates_embedding_ARK200909.txt文件中的内容并不一样

不太明白embedding过程是什么意思

二维可视化

极坐标

200px 200px

r = np.arange(0, 3.0, 0.01)
theta = 2 * np.pi * r

ax = plt.subplot(111, projection='polar')
ax.plot(theta, r, color='r', linewidth=3)
ax.set_rmax(2.0)
ax.grid(True)

ax.set_title("A line plot on a polar axis", va='bottom')
plt.show()

## example 2
import numpy as np
import matplotlib.pyplot as plt

theta = np.array([-1.5, -3, 2, 1]) # augular
r1 = 1 - np.sin(3*theta)       # radical
plt.figure(figsize = (8, 8))
ax = plt.subplot(111, polar=True, axisbg='Azure')       # background colour
ax.grid(True)                          # add the grid                 
ax.scatter(theta, r1, color='Tomato', marker= 'o',  s = 500)  
# plot the line
ax.plot(theta[:2], r1[:2],  'g-')     
ax.plot(theta[1:], r1[1:],  'b-')   
ax.set_rmax(max(r1)*1.1)                       # r maximum value
plt.show()

因特网嵌入二维极坐标的例子

## node locations
co_dict = {}
R=25.2 
k_0=1.09
for i in coordinates:
    vals = i.strip().split(' ')
    id_as = vals[0]
    k, a = vals[-2:]
    k, a = float(k.replace('D', 'E')), float(a.replace('D', 'E'))
    r=R-2*np.log(k/k_0)
    co_dict[id_as] = [r, a]

data = co_dict.values()
r1, theta = np.array(data).T 
## edge locations
edgelist = [e.strip().split(' ') for e in edges]
edge_coordinates = [[co_dict[e[0]], co_dict[e[1]]] for e in edgelist] 

## Plot
plt.figure(figsize = (10, 10))
ax = plt.subplot(111, polar=True, axisbg='Azure')       # background colour
ax.grid(True)                          # add the grid                 
# plot the lines
for edge in edge_coordinates:
    r_e, theta_e = np.array(edge).T
    ax.plot(theta_e, r_e,  color = 'green', linestyle = '-', alpha = 0.01)  
# plot the nodes
ax.scatter(theta, r1, color='Tomato', marker= 'o',  s = 10)  
ax.set_rmax(26)                       # r maximum value
# plt.show()
plt.savefig('/Users/chengjun/GitHub/datalab/internet07_hyperbolic_green.png',
            dpi = 300, bbox_inches="tight",transparent = True)

400px400px

集智研读营

  1. 2016年集智俱樂部研讀營
  2. 空间曲线
  3. https://www.researchgate.net/profile/Fragkiskos_Papadopoulos
  4. http://nbviewer.jupyter.org/github/chengjun/notebook/blob/gh-pages/slides/hyperbolic_geometry.slides.html?flush_cache=true#
  5. http://wiki.swarma.net/index.php/复杂网络的双曲几何模型 复杂网络的双曲几何模型

预读视频

  1. http://xue.duobeiyun.com/app/room/auto?roomId=jzf05d864bbb4d48bf8e730a8054ad8103 预读视频1 by 张江
  2. http://xue.duobeiyun.com/app/room/auto?roomId=jz3042d154683e4db88dd1b9a8284fe2d3 预读视频2 by 张江
  3. http://xue.duobeiyun.com/app/room/auto?roomId=jz278591a5e7e14e3f8b454b9fa825ca9c 预读视频3 by 张江
  4. http://xue.duobeiyun.com/app/room/auto?roomId=jzf1a1b147586e4926981e06b6f6d13130 预读视频4 by 吴令飞
  5. http://xue.duobeiyun.com/app/room/auto?roomId=jz320ffbe4ba72481d9b87584785f64768 预读视频5 by 吴令飞

Notebook

http://localhost:8888/notebooks/%E7%99%BE%E5%BA%A6%E4%BA%91%E5%90%8C%E6%AD%A5%E7%9B%98/Writing/HyperbolicGeometryNetwork/geometric_network_model.ipynb

参考文献

  1. Papadopoulos F, Kitsak M, Serrano M Á, et al. Popularity versus similarity in growing networks[J]. Nature, 2012, 489(7417): 537-540.
  2. Krioukov D, Papadopoulos F, Kitsak M, et al. Hyperbolic geometry of complex networks[J]. Physical Review E, 2010, 82(3): 036106.
  3. Boguñá M, Papadopoulos F& Krioukov D. Sustaining the Internet with hyperbolic mapping. Nature Communications. 2010 62 doi:10.1038/ncomms1063
  4. Serrano M A, Krioukov D, Boguná M. Self-similarity of complex networks and hidden metric spaces[J]. Physical review letters, 2008, 100(7): 078701.
  5. Brockmann D, Helbing D. The hidden geometry of complex, network-driven contagion phenomena[J]. Science, 2013, 342(6164): 1337-1342.
  6. Allard A, Serrano M, García-Pérez G, et al. The hidden geometry of weighted complex networks[J]. arXiv preprint arXiv:1601.03891, 2016.
  7. García-Pérez G, Boguñá M, Allard A, et al. Rethinking distance in international trade: World Trade Atlas 1870-2013[J]. arXiv preprint arXiv:1512.02233, 2015.
  8. M. Ángeles Serrano, Dmitri Krioukov, and Marián Boguñá 2008 Self-Similarity of Complex Networks and Hidden Metric Spaces. Phys. Rev. Lett. 100, 078701 20 February 2008; Erratum Phys. Rev. Lett. 100, 199902 (2008)http://journals.aps.org/prl/abstract/10.1103/PhysRevLett.100.078701