图 书 馆
使用Kronecker乘法对现实世界进行建模Modeling real-world networks using Kronecker multiplication |
|
| 课程网址: | http://videolectures.net/solomon_leskovec_mrw/ |
| 主讲教师: | Jure Leskovec |
| 开课单位: | 斯坦福大学 |
| 开课时间: | 2007-03-20 |
| 课程语种: | 英语 |
| 中文简介: |  |
| 课程简介: | 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? First, we propose a graph generator that is mathematically tractable and generates realistic graphs. The main idea is to use a non-standard matrix operation, the Kronecker product, to generate graphs that we refer to as ''Kronecker graphs''. We show that Kronecker graphs naturally obey all the above properties; in fact, we can rigorously prove that they do so. Once we have the model, we fit it to real graph to generate a synthetic graph that matches its properties, i.e., it has similar degree distribution, similar (small) diameter, similar spectrum, etc? We present 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, our algorithm takes linear time, by exploiting the structure of Kronecker matrix multiplication and by using sampling. Experiments on large real and synthetic graphs show that our approach recovers the true parameters and 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. //The presentation starts in Slovenian language and switches to English a few minutes into the lecture.\\ Another lecture on the same topic can be found at [[icml07_leskovec_smrg]].// |
| 关 键 词: | 合成图; 图形生成器; 非标准矩阵运算 |
| 课程来源: | 视频讲座网 |
| 最后编审: | 2019-09-22：cwx |
| 阅读次数: | 30 |