图 书 馆
基于Kronecker乘法的实图可扩展建模Scalable Modeling of Real Graphs using Kronecker Multiplication |
|
| 课程网址: | http://videolectures.net/icml07_leskovec_smrg/ |
| 主讲教师: | Jure Leskovec |
| 开课单位: | 斯坦福大学 |
| 开课时间: | 2007-06-23 |
| 课程语种: | 英语 |
| 中文简介: |  |
| 课程简介: | Given a large, real graph, how can we generate a synthetic graph that matches its properties, i.e., it has similar degree distribution, similar (small) diameter, similar spectrum, etc? We propose to use "Kronecker graphs", which naturally obey all of the above properties, and we present KronFit, a fast and scalable algorithm for fitting the Kronecker graph generation model to real networks. A naive approach to fitting would take super-exponential time. In contrast, KronFit takes linear time, by exploiting the structure of Kronecker product and by using sampling. Experiments on large real and synthetic graphs show that KronFit indeed mimics very well the patterns found in the target graphs. Once fitted, the model parameters and the resulting synthetic graphs can be used for anonymization, extrapolations, and graph summarization. |
| 关 键 词: | 超指数时间; 线性时间; 合成图 |
| 课程来源: | 视频讲座网 |
| 最后编审: | 2019-04-17：lxf |
| 阅读次数: | 57 |