2012-01-01から1年間の記事一覧
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, Heid…
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…
http://arxiv.org/pdf/1109.6642v3.pdf http://michaelschaub.github.com/MarkovZoomingMap/
辺が追加されることのみが考慮されるモデル・アルゴリズムが横行している．なんでなんだろう？とずっと思っていた．辺が一方的に追加されていくネットワークの成長のデータセットを公開している Alan Mislove の博論を見た． 6.2 Growth dominates network e…
LU 分解 1+(n-1) の形に分解して立式して冷静になり，再帰的に分解すればよい べき乗法 ランダムではじめる → 最大固有値のベクトルが求まる． 初期値のベクトル x_0 = Σc_i u_i だと思うと，x_k = (Σλ_i^k c_i u_i) / 定数 だから初期値のベクトルがなんか…
http://www.cc.gatech.edu/~mihail/index8802.html http://www.cs.cornell.edu/Courses/cs685/2002fa/ http://www-net.cs.umass.edu/cs691s/ https://computation.llnl.gov/casc/people/chow/pubs/levdiff-aaai.pdf http://www.informatik.uni-trier.de/~ley…
面白そうなので気が向いた時に調べる．随時情報追加予定． 基礎 http://en.wikipedia.org/wiki/Graph_drawing これを読むぞ！ http://www.csse.monash.edu.au/hons/se-projects/2006/Kieran.Simpson/output/html/node2.html コレも気になる！ なんかのソフト…
Time-Critical Influence Maximization in Social Networks with Time-Delayed Diffusion Process highly influential users を探したい time-critical influence maximization 締め切り付き Independent Cascade model (IC) 時間の遅延のモデルっぽい submo…
データセット http://cactus.nci.nih.gov/index.html ここから手に入る vertices: atoms, edges: pairs of covalently-linked atoms 性質 小さいのがいっぱい：〜100 頂点ぐらい path-width が小さい：３以下が 99% を占める！？
Rachit Agarwal, Matthew Caesar, Philip Brighten Godfrey, and Ben Y. Zhao. 2012. Shortest paths in less than a millisecond. In Proceedings of the 2012 ACM workshop on Workshop on online social networks (WOSN '12). ACM, New York, NY, USA, 37…
Yufei Tao, Cheng Sheng, and Jian Pei. 2011. On k-skip shortest paths. In Proceedings of the 2011 ACM SIGMOD International Conference on Management of data (SIGMOD '11). ACM, New York, NY, USA, 421-432. DOI=10.1145/1989323.1989368 http://do…
Ruoming Jin, Ning Ruan, Yang Xiang, and Victor Lee. 2012. A highway-centric labeling approach for answering distance queries on large sparse graphs. In Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data (SIGM…
"K-Reach: Who is In Your Small World" by James Cheng, Zechao Shang, Hong Cheng, Haixun Wang, Jeffrey Xu Yu. VLDB 2012.
Lovro Šubelj, Marko Bajec. Software Systems through Complex Networks Science: Review, Analysis and Applications. SoftwareMining'12.
7 3 次方程式の解の公式 L, R がすごいらしい（ラグランジュ・リゾルベントっていうらしい） 頑張って二次方程式の解の公式を使っていた 8 拡大次数 [Q(√2) : Q] = Q(√2) / Q の拡大次数 拡大次数の積の定理 [Q(√2, √3) : Q] = [Q(√2) : Q] * [Q(√2)(√3) : Q…
http://www.gictf.jp/doc/20120709GICTF.pdf
3 群 閉性，結合法則，単位元，逆元 巡回群 アーベル群 4 円分多項式，円分方程式 5 作図可能点，作図可能数 作図可能数 = 加減乗除と開閉の繰り返しで作れる数 20度は作図できない… cos20°は作図可能数でない 6 線形空間 スカラー倍，スカラー倍の分配法則…
Catherine C. McGeoch, A Guide to Experimental Algorithmics, Chapter 4.
Catherine C. McGeoch, A Guide to Experimental Algorithmics, Chapter 2.ちゃんとした実験を設計しましょう
演習 3 のネタが尽きつつあるので頑張って探す必要があるとりあえず列挙してみた
Anand Rajaraman and Jeff Ullman, Mining of Massive Datasets, Chapter 5.基礎っぽいけど，この辺，グラフアルゴリズムの界隈とはちょっと違う界隈だよな〜
「複雑ネットワーク」とは何か―複雑な関係を読み解く新しいアプローチ (ブルーバックス)作者: 増田直紀,今野紀雄出版社/メーカー: 講談社発売日: 2006/02/21メディア: 新書購入: 8人 クリック: 59回この商品を含むブログ (72件) を見る このように、エリート…
http://google-sparsehash.googlecode.com/svn/trunk/doc/implementation.htmlgoogle::dense_hash_map 使ってみたら速かった，それの実装についての説明
Ken Wakita and Toshiyuki Tsurumi. 2007. Finding community structure in mega-scale social networks: [extended abstract]. In Proceedings of the 16th international conference on World Wide Web (WWW '07). ACM, New York, NY, USA, 1275-1276. DOI…
Min-Joong Lee, Jungmin Lee, Jaimie Yejean Park, Ryan Hyun Choi, and Chin-Wan Chung. 2012. QUBE: a quick algorithm for updating betweenness centrality. In Proceedings of the 21st international conference on World Wide Web (WWW '12). ACM, Ne…
やすみ
Alan Mislove, Massimiliano Marcon, Krishna P. Gummadi, Peter Druschel, and Bobby Bhattacharjee. 2007. Measurement and analysis of online social networks. In Proceedings of the 7th ACM SIGCOMM conference on Internet measurement (IMC '07). A…
Nan Wang, Jingbo Zhang, Kian-Lee Tan, and Anthony K. H. Tung. 2010. On triangulation-based dense neighborhood graph discovery. Proc. VLDB Endow. 4, 2 (November 2010), 58-68.
Ittai Abraham, Amos Fiat, Andrew V. Goldberg, and Renato F. Werneck. 2010. Highway dimension, shortest paths, and provably efficient algorithms. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '10)…
Konstantin Tretyakov, Abel Armas-Cervantes, Luciano García-Bañuelos, Jaak Vilo, and Marlon Dumas. 2011. Fast fully dynamic landmark-based estimation of shortest path distances in very large graphs. In Proceedings of the 20th ACM internatio…
