【DM论文阅读杂记】复杂社区网络
Paper Title
Community Structure in Time-Dependent, Multiscale, and Multiplex Networks
Basic algorithm and main steps
Basic ideas
The paper generalizes the determination of community structure via quality functions to multislice networks, and derive a null model in terms of stability of communities under Laplacian dynamics.
Derivation of the quality function
Restricted our attention to unipartite, undirected network slices \((A_{ijs}= A_{jis})\) and couplings $(C_{jrs} = C_{jsr}) $ .
$ \omega $: Slice coupling strengths.
$ A_{ijs} $ : at slice \(s\), the connection node \(i\) and node \(j\)
$ C_{jrs} $: the connection between slice \(r\) and slice \(s\)
$ k_{js} = \sum_i A_{ijs} $ : the degree / strength of the node $ j $ on slice $ s $
$ C_{js} = \sum_r C_{jsr} $ : the strength across slice $ s $
multiple strength : $ \kappa {js} = k + C_{js} $
The expected weight of the edge between $ i $ and $ j $ under Laplacian dynamics:
\]
Using the steady-state probability distribution
$ p^*{jr} = \kappa / 2\mu , ( 2\mu = \sum_{jr} \kappa_{jr} ) $
$ \gamma_s $: revolution parameter
Conditional propability:
\]
$ m_s = \sum_j k_{js} $
Quality function:
\]
Recover null model
Recovered the standard null model for directed networks (with a resolution parameter) by generalizing the Laplacian dynamics to include motion along different kinds of connections, giving multiple resolution parameters and spreading weights.
Motivation
- In terms of community detection, departed null models have not been available for time-dependent networks.
- One solution: piece together the structures obtained at different times or have abandoned quality functions in favor of such alternatives as the Minimum
Description Length principle. - Another solution: tensor decomposition, without qualtiy-function.
Contribution
- Generalize the determination of community structure via quality functions to multislice networks, removing the limits.
- Formulate a null model in terms of stability of communities under Laplacian dynamics.
My own idea
Some analysis
- Fig 2 is the experiment result on the dataset of the Zachary Karate Club network. There is 34 nodes and 16 slices (with resolution parameters $\gamma_s $= { 0 . 25, 0 . 5 , …, 4 } and $\omega $= {0,0.1,1}). Other things being equal, the larger \(\gamma\) is, the more communities is. The $ \omega $ means tighter connections among time slices. The horizontal axis is $ \gamma $, and the vertical axis is the 34 members. For any one of the three pictures, the number of communities increases as the $\gamma $ increases. With $\omega $ = 0.1,1, with \(\gamma\) increasing, nodes assigned to the same may keep in the same communities or be partitioned to different communities. However, comparing to the ones with larger slice coupling strengths( the second and the third picture ), the one ignoring slice coupling ( the first picture, with $ \omega $ = 0 ) will lead to messy clustering results (eg. both the \(\gamma\) = 0.25 and the \(\gamma\) have two communities, but they are not the same two communities) . Therefore, taking slice coupling strengths into consideration can improve the performance of the community detection.
Confuse
- What confuses me is the details of derivating the quality function.
Shortcoming
- The paper lacks comparing the performance of their novel algorithm with others.
Others
I have learnt the null model and quality function of community detection in one dimesion, which is in the monority and restricted greatly. Through this paper, I know the methology in mutiscale and mutiplex networks.
\[Q = \frac{1}{2m}\sum_{s \in S}\sum_{i, j \in s}(A_{ij} - \frac{k_i k_j}{2m}) =\\
= \frac{1}{2m}\sum_{i, j}(A_{ij} - \frac{k_i k_j}{2m}) \delta(g_i,g_j)
\]$ \delta(g_i, g_j )$ = 1 if nodes \(i\) and \(j\) are in the same communities and 0 otherwise.
Unfinished: reproduct the code and results.
最新文章
- 队列&;生产者消费者
- NOI 动态规划题集
- oc面向对象特性: 多态
- linux 下 ntfs移动硬盘挂载
- wordpress添加文章浏览统计(刷新不重复)
- CSS——伪元素与伪类
- SQL经典题
- shell笔记(基本知识)
- Oracle的Net Configuration Assistant 配置
- 如何为linux释放内存和缓存
- Java 中 for each
- WebApi系列(从.Net FrameWork 到 .Net Core)
- kali linux工具--信息批量收集工具theharvester
- jmeter数据库连接配置
- C++读写图片数据转成Base64格式
- Mac-Navicat Premium For Mac 12 破解 - [数据库可视化工具,亲测完美破解]
- 【C#】C#线程_基元线程的同步构造
- jquery裁剪图片插件cropit示例
- www.jqhtml.com 前端框架特效
- java Swing小知识点