匹配生长随机几何图模型

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

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

Clone this wiki locally

http://wiki.swarma.net/index.php/%E5%8C%B9%E9%85%8D%E7%94%9F%E9%95%BF%E9%9A%8F%E6%9C%BA%E5%87%A0%E4%BD%95%E5%9B%BE%E6%A8%A1%E5%9E%8B

Despite some pioneering modelling approaches proposed for specific systems, whether there exists some general mechanisms that account for the origins of such scaling behaviours in different contexts, especially in socioeconomic systems, remains an open question.

Table of Contents

the hyperbolic space model for construction of scale-free networks

Papadopoulos, F., Kitsak, M., Serrano, A., Boguna, M. & Krioukov, D. Popularity versus similarity in growing networks. Nature 489, 537–540 (2012).

the hidden geometry of complex networks

Brockmann, D. & Helbing, D. The hidden geometry of complex, network-driven contagion phenomena. Science 342, 1337–1342 (2013).

a spatial-constrained attachment (SCA) model

Zhang, Jiang; Xintong Li, Xinran Wang, Wen-Xu Wang, Lingfei Wu (2015). "Scaling behaviors in the growth of networked systems and their geometric origin". Scientific Reports 5: 9767. http://www.nature.com/articles/srep09767

600px

Geometric graph

其实,Penrose, Mathew 在2003年就已经提出过Random Geometric Graphs, Oxford Studies in Probability, 5, 2003.[1]

Geometric: Generators for geometric graphs.

  • random_geometric_graph(n, radius[,]) Returns a random geometric graph in the unit cube.
  • geographical_threshold_graph(n, theta[,]) Returns a geographical threshold graph.
  • waxman_graph(n[,]) Return a Waxman random graph.
  • navigable_small_world_graph(n[,]) Return a navigable small-world graph.
http://networkx.github.io/documentation/latest/_modules/networkx/generators/geometric.html#random_geometric_graph

例如:

 random_geometric_graph(n, radius, dim=2, pos=None): """Returns a random geometric graph in the unit cube. The random geometric graph model places ``n`` nodes uniformly at random in the unit cube. Two nodes are joined by an edge if the Euclidean distance between the nodes is at most ``radius``.
#---------------------------------------------------------------------------
  1. Random Geometric Graphs
  2. ---------------------------------------------------------------------------
def random_geometric_graph(n, radius, dim=2, pos=None): """Returns a random geometric graph in the unit cube. The random geometric graph model places ``n`` nodes uniformly at random in the unit cube. Two nodes are joined by an edge if the Euclidean distance between the nodes is at most ``radius``. Parameters ---------- n : int Number of nodes radius: float Distance threshold value dim : int, optional Dimension of graph pos : dict, optional A dictionary keyed by node with node positions as values. Returns ------- Graph Examples -------- Create a random geometric graph on twenty nodes where nodes are joined by an edge if their distance is at most 0.1:: >>> G = nx.random_geometric_graph(20, 0.1) Notes ----- This algorithm currently only supports Euclidean distance. This uses an `O(n^2)` algorithm to build the graph. A faster algorithm is possible using k-d trees. The ``pos`` keyword argument can be used to specify node positions so you can create an arbitrary distribution and domain for positions. For example, to use a 2D Gaussian distribution of node positions with mean (0, 0) and standard deviation 2:: >>> import random >>> n = 20 >>> p = {i: (random.gauss(0, 2), random.gauss(0, 2)) for i in range(n)} >>> G = nx.random_geometric_graph(n, 0.2, pos=p) References ---------- .. [1] Penrose, Mathew, Random Geometric Graphs, Oxford Studies in Probability, 5, 2003. """ 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() pu = du['pos'] 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
  1. Zhang, Jiang; Xintong Li, Xinran Wang, Wen-Xu Wang, Lingfei Wu (2015). "Scaling behaviors in the growth of networked systems and their geometric origin". Scientific Reports 5: 9767. http://www.nature.com/articles/srep09767.
  2. Zhang, Jiang 2012. Growing Random Geometric Graph Models of Super-linear Scaling Laws. http://arxiv.org/abs/1212.4914.
  3. Li, Xintong; Xinran Wang, Jiang Zhang (2015). "Allometric Scaling, Size Distribution, and Pattern Formation of Natural Cities". Palgrave Communications 1: 15017. http://www.palgrave-journals.com/articles/palcomms201517.