Visual detection of structural changes in time-varying graphs using persistent homology
Basic knowledge:
1. what is time-varying graphs?
time-varying graph VS static graph.
a time-varying graph - an ordered sequence of graph instances.
2. how to measure similarity or dissimilarly between graphs?
way1: map the graphs into a feature space and then define distances on this space.
way2: graph comparison with known node correspondences.
way3: graph comparison without unknown node correspondences.
3. how to visualize time-varying graphs?
two major categories: animation and timelines.
4. how to analysis static graph and visualize static graphs?
Static graph visualization: use variations on node-link visualizations to display graphs.
For dense/clutter graphs, -------> edge bundling.
Questions:
2. how to use persistent homology to capture topological features of time-varying graphs.
- how to embed the graph into a metric space. then topological techniques can be applied into this metric space.
Methodology:
basic rules: use persistent homology to identify and compare features in a time-varying graph.
Their visual design goal: identify high-level structural changes in a time-varying graph.
time-varying graph: an ordered sequence of static graph instances.
Methods:
- each graph is embedded into a metric space. G = {G_1, G_2,... G_i...} This yields a symmetric distance matrixd d_i, d_sp(x,y) is the shortest path distance between node x and node y.
- extract topological features from each G_i by using persistnet homology to its metric space.
- calculate the distance between persistence diagrams and then project them by using classical multi-dimensional scaling(MDS).
Knowledgebase:
1. Dijkstra's algotithm: 迪杰斯特拉算法使用了广度优先搜索解决赋权有向图的单源最短路径问题。
2. Quantitative Journey blog about TDA: topological data analysis
最新文章
- sed awk 样例
- web前端性能优化指南(转)
- zookeeper系列之通信模型(转)
- Lamp学习笔记
- USB HID描述符【转】
- STL序列式容器
- 【BZOJ2741】【块状链表+可持久化trie】FOTILE模拟赛L
- SQL 查询的执行过程
- Struts2,Spring,Hibernate三大框架的整合(SSH)
- dfs和bfs的简单总结
- 安卓 异步线程更新Ui
- 配置程序成为Linux服务
- ffplay.c函数结构简单分析(画图)
- RPC调用与GC垃圾回收
- silverlight用Encoding.UTF8读取shape文件的中文属性值 出现乱码
- Testng用例失败重新运行
- LOJ-10102(求A到B之间的割点)
- delphi 演示数据路径
- C++ Primer读书笔记(2)
- require('nw.gui') 失效问题