Weighted Graphs and Disconnected Components
Weighted Graphs and Disconnected Components
复制标题
加权图和断开的组件
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
C. Faloutsos
中科院分区：
文献类型：
--
作者：
Mary McGlohon;L. Akoglu;C. Faloutsos
绝大多数早期的工作都集中在图都是连接的（通常通过忽略所有，但巨大的连通分量），和未加权。在这里，我们研究了大量的，真实的，加权图，并报告了令人惊讶的发现的方式，新的节点加入和形成链接的社会网络。激励性的问题如下：图形形式的连接组件如何随着时间的推移而变化？新节点加入网络后会发生什么-重复边有多常见？我们研究了许多不同的，真实的图（引用网络，社交媒体网络，互联网流量等），并作出以下贡献：（a）我们观察到，非巨型连接组件似乎稳定的大小，（B）我们观察到的边缘上的权重遵循几个幂律与令人惊讶的指数，（c）我们提出了一个直观的，生成模型的图增长，遵守观察到的模式。
The vast majority of earlier work has focused on graphs which are both connected (typically by ignoring all but the giant connected component), and unweighted. Here we study numerous, real, weighted graphs, and report surprising discoveries on the way in which new nodes join and form links in a social network. The motivating questions were the following: How do connected components in a graph form and change over time? What happens after new nodes join a network– how common are repeated edges? We study numerous diverse, real graphs (citation networks, networks in social media, internet traffic, and others); and make the following contributions: (a) we observe that the non-giant connected components seem to stabilize in size, (b) we observe the weights on the edges follow several power laws with surprising exponents, and (c) we propose an intuitive, generative model for graph growth that obeys observed patterns.