Hatena::ブログ(Diary)

(iwi) 備忘録

 

2013-04-12

移転

はてなブログに移転します

http://iwiwi.hatenadiary.jp/

(今更ですが,本当は大昔に書いたのですが投稿されずバックアップにだけ残っていました)

2013-01-21

Methods to Find Overlapping Communities

Community detection in graphs http://arxiv.org/abs/0906.0612

通常の手法は,1 頂点はちょうど 1 つのコミュニティに所属する.そうではなく,1 頂点が複数のコミュニティに所属し得るようなコミュニティ列挙の手法

続きを読む

2013-01-16

2013-01-15

2013-01-11

2013-01-10

2013-01-09

2013-01-08

2013-01-07

2013-01-04

2012-12-26

Compact routing in power-law graphs

Wei Chen, Christian Sommer, Shang-Hua Teng, and Yajun Wang. 2009. Compact routing in power-law graphs. In Proceedings of the 23rd international conference on Distributed computing (DISC'09), Idit Keidar (Ed.). Springer-Verlag, Berlin, Heidelberg, 379-391.

実際にはTALGに出しているらしき原稿の方を読んだ. こっちだと数式がレンダリングされます http://iwi.tc/wiki/index.php?%E8%AB%96%E6%96%87%2F%E3%82%B0%E3%83%A9%E3%83%95%E7%90%86%E8%AB%96%E7%B3%BB%2FA%20Compact%20Routing%20Scheme%20and%20Approximate%20Distance%20Oracle%20for%20Power-law%20Graphs

続きを読む

2012-12-21

A model-based approach to attributed graph clustering

Zhiqiang Xu, Yiping Ke, Yi Wang, Hong Cheng, and James Cheng. 2012. A model-based approach to attributed graph clustering. In Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data (SIGMOD '12). ACM, New York, NY, USA, 505-516. DOI=10.1145/2213836.2213894 http://doi.acm.org/10.1145/2213836.2213894

続きを読む

2012-12-20

2012-12-15

ネットワークの成長

辺が追加されることのみが考慮されるモデル・アルゴリズムが横行している.なんでなんだろう?とずっと思っていた.

辺が一方的に追加されていくネットワークの成長のデータセットを公開している Alan Mislove の博論を見た.

6.2 Growth dominates network evolution

In all of the networks we examined, we found that link addition was significantly more frequent than link removal. In particular, we found that in Flickr, link additions exceeded link removals in our data sets at a rate of 2.43:1. Similar characteristics were observed in the other networks we studied: in YouTube-U, the ratio of link additions to removals was 3.71:1, and in the Internet, we found that the ratio was 2.06:1.


うーん……一番大きくても 3.71:1 って辺の削除も結構大きいと思うが……

2012-12-10