Greedy Algorithms and Local Search (Chapter 2, The Design of Approximation Algorithms)
2.1 Scheduling jobs with deadlines on a single machine
- 問題：スケジューリング．max(締切を過ぎた時間) を最小化したい
- NP-hard (0 以下か否かの判定だけでも strongly NP-hard)
- 以下，d_i < 0 と仮定する
- アルゴリズム：Greedy に締切が近いやつからやっていく
- 近似値の評価
- 最適値の lower-bound を得る
- 近似値の upper-bound を得る
省略：大体おなじ
- 2.2 The k-center problem
- 2.3 Scheduling jobs on identical parallel machines
2.4 The traveling salesman problem
2.5 Maximizing flota in bank accounts
- 問題概要
- 銀行を k 個選んで float の和を最大化せよ
- 近似アルゴリズム：Greedy
- 証明：submodular
An Introduction to Approximation Algorithms (Chapter 1, The Design of Approximation Algorithms)
Set Cover 問題をひたすら扱う
- Deterministic LP rounding
- 要素の最大次数を f とする
- LP を解き，1/f 以上になっているやつを 1 にする
- f 近似
- Deterministic dual LP rounding
- 相補性定理
- Primal-dual を使うと簡単に Dual 解が求まる
- Greedy
- 「コスト/新たにカバーできる要素数」が最大のものをとっていく
- H_n 近似（タイト）
- Randomized LP rounding
- 定数 c
- 集合 j に対し，「確率 x^*_j で表が出るコイン」を c ln n 回振って，表が出たら採用
- 確率 1/n^{c-1} でカバーされる
- コストの期待値 c ln n
- 「コスト | カバーされる」の期待値 2c ln n
関数ポインタと関数オブジェクトと仮想関数の速度比較
趣旨
アルゴリズム内の処理の一部を指定させる一般的な方法には以下がある．
- 関数ポインタを使う (qsort 等)
- 関数オブジェクトを使う (std::sort 等)
- 仮想関数を使う
これらで性能がどう変化するかを測定した．
結果概要
wandbox にて実験した：http://melpon.org/wandbox/permlink/H7VjfOqgiEh4XWCP
pointer: 5.036541 sec
template: 3.373498 sec
virtual: 4.716775 sec
inline: 3.322171 sec
- pointer とは関数ポインタで指定した場合
- template とは関数オブジェクトで指定した場合
- virtual とは仮想関数を使って指定した場合
- inline とは指定なしでベタ書きした場合，一番最適化が効くはず
結果は template が inline とほぼ同等の速度で他より有意に高速であった．予想通りですね．これは，最適化の対象となるコードがベタ書きにかなり近くなり，インライン化等を含む最適化が効果的に働くから．
CPLEX 色々
探索ノード数を得る
IloCplex cplex(model);
...
cplex.solve();
cout << "Nodes: " << cplex.getNnodes() << endl;
カット数を得る
cout << "Cuts: " << cplex.getNcuts(IloCplex::CutClique) << endl;
- http://pic.dhe.ibm.com/infocenter/cosinfoc/v12r4/index.jsp?topic=%2Filog.odms.ide.help%2Frefdotnetopl%2Fhtml%2FT_ILOG_CPLEX_Cplex_MIPCallback.htm
- http://pic.dhe.ibm.com/infocenter/cosinfoc/v12r5/index.jsp?topic=%2Filog.odms.ide.help%2Frefjavaopl%2Fhtml%2Filog%2Fcplex%2FIloCplex.CutType.html
- getNほげcuts 系は deprecated http://www.hpc.science.unsw.edu.au/files/docs/ilog/cplex/12.1/html/Content/Optimization/Documentation/CPLEX/_pubskel/ps_releasenotescplex13.html
ruby -ne 'puts "IloCplex::" + $_.split("=")[0].strip + ","' int num_cuts = 0;
for (IloCplex::CutType c : {
IloCplex::CutCover,
IloCplex::CutGubCover,
IloCplex::CutFlowCover,
IloCplex::CutClique,
IloCplex::CutFrac,
IloCplex::CutMCF,
IloCplex::CutMir,
IloCplex::CutFlowPath,
IloCplex::CutDisj,
IloCplex::CutImplBd,
IloCplex::CutZeroHalf,
IloCplex::CutLocalCover,
IloCplex::CutTighten,
IloCplex::CutObjDisj,
IloCplex::CutLiftProj,
IloCplex::CutUser,
IloCplex::CutTable,
IloCplex::CutSolnPool}) {
num_cuts += cplex.getNcuts(c);
}
cout << "Cuts: " << num_cuts << endl;
厳密解を求めさせる
cplex.setParam(IloCplex::Param::MIP::Tolerances::MIPGap, 0.0);
並列を封じる
cplex.setParam(IloCplex::Param::Threads, 1);
国際ジャーナル
そろそろジャーナルにも論文を出してみたいのですが，本当にどこがいいのか分からない……ﾀﾞﾚｶﾀｽｹﾃｰ
DB 系
ランキング http://academic.research.microsoft.com/RankList?entitytype=4&topdomainid=2&subdomainid=18&last=10
ACM TODS
多分超有名？でも会議論文からの差分を 30% 要求される．通る気がしない．
http://tods.acm.org/Authors.html#ManuscriptPreparation
A submitted manuscript that is based on one or more previous publications by one or more of the authors should have at least 30% new material. (略)
VLDB Journal
やっぱりこっちも超有名？ こっちも 30% の差分を要求される．
http://vldb.org/vldb_journal/index.php/author-guidelines/submission-rules
A submission that substantially overlaps the authors' previous refereed or copyrighted publications, such as an extended version of a conference paper, must contain at least 30% significant new content.
IEEE TKDE
よく見かける気がする．見かける数が多いということはちょっとは緩いのではないかと推測していたが，なんとここでも差分が要求されるのであった……
http://www.computer.org/portal/web/peerreviewjournals/author
Papers previously published in conference proceedings, digests, preprints, or records are eligible for consideration provided that the papers have undergone substantial revision, and that the author informs the journal coordinator at the time of submission.
ていうか conference どころか preprint からも差分を要求するってなんかもう意味が分からないんだけれどなんでこういう慣習がまかり通ってるんだ……．でも revision だけでいいなら新しい貢献はなくてもいい？
Please be aware that editors and reviewers are required to check the submitted manuscript to determine whether a sufficient amount of new material has been added to warrant publication.
...
then you are required to cite the previous work(s) and clearly indicate how the new submission offers substantively novel or different contributions beyond those of the previously published work(s).
そんなことはなさそうだった（絶望）
その他
論文を殆ど見たことが無いけれど以下のようなジャーナルがあるようだ．
- Information Systems (IS)
- 出版社がよく見かける（緑色のサイトの） ELSEVIER である．よく知らない所よりは安心できる．
- Information Systems Research (ISR)
- 謎の出版社．名前がややこしい．
- Knowledge and Information Systems Journal (KAIS)
- Journal of Intelligent Information System (JIIS)
- Data Mining and Knowledge Discovery (DMKD/DAMI)
James Cheng 先生 (http://www.cse.cuhk.edu.hk/~jcheng/publications.html) は駆け出しの頃はこれらのジャーナルを利用していた模様．KAIS 2 件，JIIS 1 件，DMKD 1 件．
その他
World Wide Web Journal
国際会議 World Wide Web に対応するジャーナルなのではないか，超ハイジャーナルなのでは，と思わせておいて多分実はそこまでのレベルではないっぽい予感がする（よく知らないけど）．結構見かける．
http://www.springer.com/computer/database+management+%26+information+retrieval/journal/11280
Submission of a manuscript implies: that the work described has not been published before;
ん？
Internet Mathematics
よく知らないけれどたまに見かける気がする．
- http://projecteuclid.org/euclid.im
- http://www.tandfonline.com/action/authorSubmission?journalCode=uinm&page=instructions#.Uu-nL3V_vj4
Please note that Internet Mathematics uses CrossCheck™ software to screen papers for unoriginal material. By submitting your paper to Internet Mathematics you are agreeing to any necessary originality checks your paper may have to undergo during the peer review and production processes.
conference paper をベースに提出したら unoriginal 判定されてしまうのか？
結論
どのジャーナルもなんか originality とか novelty を要求していてわけがわからなくなった．もしやこちらの界隈では best papers に選ばれて special issue に招待されない限り会議論文をそのままジャーナルなんて出せない？
というかびっくりしたけれどかの有名な Jure Leskovec も実はジャーナルは 11 本しか出してない？（DBLP 調べ）一方学会論文は 70 本を超える．ジャーナルはあまり要らないのか？
しかし喜連川先生はジャーナルも 60 本を超えていた，流石．（会議は200本超え）
ジャーナルとは一体何なのか……（続く）
SDM'14 Accepted Papers
- VoG: Summarizing and Understanding Large Graphs
- Local Learning for Mining Outlier Subgraphs from Network Datasets
- Triangle counting in streamed graphs via small vertex covers
- Laplacian Spectral Properties of Graphs from Random Local Samples
- DAVA: Distributing Vaccines over Networks under Prior Information
- A Deep Learning Approach to Link Prediction in Dynamic Networks
- Multi-Task Feature Selection on Multiple Networks via Maximum Flows
- Make It or Break It: Manipulating Robustness in Large Networks
EDBT'14 Accepted Papers
http://www.edbticdt2014.gr/index.php/edbt-accepted-papers
グラフかつとても興味がある
- 166 Renê R. Veloso, Loïc Cerf, Wagner Meira Junior and Mohammed J. Zaki Reachability Queries in Very Large Graphs: A Fast Refined Online Search Approach
- 269 Francesco Bonchi, Aristides Gionis, Francesco Gullo and Antti Ukkonen Distance oracles in edge-labeled graphs
- 11 Chenghui Ren, Luyi Mo, Ben Kao, Reynold Cheng and David W. Cheung CLUDE: An Efficient Algorithm for LU Decomposition Over a Sequence of Evolving Graphs
- LU 分解とかそもそも大規模だと無理やろ
- 241 Tarique Anwar, Chengfei Liu, Hai L Vu and Christopher Leckie Spatial Partitioning of Large Urban Road Networks
- 343 Cigdem Aslay, Nicola Barbieri, Francesco Bonchi and Ricardo Baeza-Yates Online Topic-aware Influence Maximization Queries
グラフであるが普通
- 118 Dritan Bleco and Yannis Kotidis Graph Analytics on Massive Collections of Small Graphs
- 404 Arijit Khan, Francesco Bonchi, Aris Gionis and Francesco Gullo Fast Reliability Search in Uncertain Graphs
- 156 Chengyuan Zhang, Ying Zhang, Wenjie Zhang, Xuemin Lin, Muhammad Cheema and Xiaoyang Wang Diversified Spatial Keyword Search On Road Networks
- 88 Sadegh Nobari, Panagiotis Karras, Hweehwa Pang and Stéphane Bressan L-opacity: Linkage-Aware Graph Anonymization
- 329 Tamir Tassa and Francesco Bonchi Privacy Preserving Estimation of Social Influence
- 417 Aston Zhang, Xing Xie, Kevin Chen-Chuan Chang, Carl A. Gunter, Jiawei Han and Xiaofeng Wang Privacy Risk in Anonymized Heterogeneous Information Networks
ICDE'14 Accepted Papers
http://ieee-icde2014.eecs.northwestern.edu/accepted.html
特に気になるグラフ系
- 533 Fast Incremental SimRank on Link-Evolving Graphs
- 551 Fast Top-K Path-based Relevance Query on Massive Graphs
- 203 Efficient Top-K Closeness Centrality Search
- 233 Random-walk Domination in Large Graphs
- 47 Incremental Cluster Evolution Tracking from Highly Dynamic Network Data
- 269 Top-K Interesting Subgraph Discovery in Information Networks
そのほか仕事で関係しそうなグラフ系を抜き出します
- 167 Answering Graph Pattern Queries Using Views
- 173 GLog: A High Level Graph Analysis System Using MapReduce
- 242 Continuous Pattern Detection over Billion-Edge Graph Using Distributed Framework
- 248 How to Partition a Billion-Node Graph
- 257 Efficient and Accurate Query Evaluation on Uncertain Graphs via Recursive Stratified Sampling
- 374 Subgraph Pattern Matching over Uncertain Graphs with Identity Linkage Uncertainty
- 532 Large-Scale Frequent Subgraph Mining in MapReduce
- 571 Query Optimization of Distributed Graph Pattern Matching
それ以外
- 63 A General Algorithm for Subtree Similarity-Search
- 646 Optimal Hierarchical Layouts for Cache-Oblivious Search Trees
Delineating Social Network Data Anonymization via Random Edge Perturbation (CIKM'12)
- 問題：匿名化
- 手法 random edge pertubation
- 一定確率 μ で辺の有無を入れ替える (perturbation probability)
- 特徴量の推定
- 特徴量は，変化してしまうが，推定ができる（最尤推定する）
- density, degree distribution, transitivity, modularity
- 独立でランダムに変更してるので簡単
- 攻撃
- walk-based attack に新たなテクニックを追加 (probabilistic attack)
- interval degree check
- error-tolerant edge check
- もう少し頑張る一般的な攻撃というのもあるらしい
- 実験
- とても小さいグラフでしかできない
- （かなり dense になってしまうのであたりまえ）
Scalable kernels for graphs with continuous attributes (NIPS'13)
田部井さんのスライドを見ればだいたい分かる http://www.slideshare.net/tbyasu/nips2013-scalable-kernels-for-graphs-with-continuous-attributes
- 問題
- グラフ同士のカーネル
- しかもグラフの頂点には連続値ベクトルの属性がついている
- 辺には重み（長さ）が付いている
- 既存手法は O(n^4) のなんか微妙そうなやつ
- 頂点対の対を全通り考える
- 提案手法 GraphHopper
- 同じ長さ（頂点数）の最短路同士で類似度を考える
- 各頂点について長さ k のパスの i 番目に出てくる回数みたいなのが求められればあとは重み付き和になって O(n^2) で求まるようになってる
Random Graphs (Chapter 11, Graph Theory)
The notion of a random graph
- Erdos-Renyi model $G(n, p)$
- $q = 1 - p$ とおく
- 独立集合 $ P[\alpha(G) \geq k] \leq {n \choose k}q^{k \choose 2} $
- クリーク $ P[\omega(G) \geq k] \leq {n \choose k}p^{k \choose 2} $
- Ramsey number R(r)
- $R(r)$ 頂点以上のグラフは必ず $K^r$ か $\overline{K^r}$ を含む
- $R(r) > n > 2^\frac{k}{2}$ を示す
- $G(n, 1/2)$ を考えて，$P[\alpha(G) \geq k] + P[\omega(G) \geq k] < 1$ となる
- 従って，k 以上のクリークも独立集合も持たないかもしれない
The probabilistic method
- 定理：任意の k について，$g(H)>k$ かつ $\chi(H)>k$ なる $H$ が存在する
- $g(G)$ := girth (最短のサイクル長)
- $\chi(G)$ := 彩色数
- つまり，ローカルに見たら木みたいなのに，彩色数も大きいっていうグラフがある！
- 証明
- 最初に考える事
- $p$ を小さくすると，$g(G)$ は大きくなる
- 彩色数の代わりに独立集合を考えて，$n/k$ より大きい独立集合が 1 個はないといけない
- そういうのがなければ，彩色数は $k$ より大きい
- $p$ を大きくすると，独立集合はなくなって $\chi(G)$ は大きくなる
- でも，さっきみたいに簡単に和等で証明できるような良い $p$ は存在しない（むずい！）
- そこで
- $n/2$ 個しか short cycle がなく，サイズ $n/2k$ より大きい独立集合がないものをつくる
- 全 cycle から頂点を削除して $H$ を得る
- Markov's inequality: $P[X \geq a] \leq \frac{E(X)}{a}$ （独立じゃない時に便利！）
- サイクル同士はかぶったりするから独立じゃないので面倒だが Markov's inequality を使う
- 最初に考える事
Properties of almost all graphs
- $n \rightarrow \infty$ の時 $G$ がある性質を持つ確率が 1 や 0 に収束するものを考える
- 任意のグラフ $H$ について，$H$ を部分誘導グラフとして含む確率は 1 に収束
- $k$-connected である確率は 1 に収束
Zero-one laws
First-order logic で書ける性質は確率が必ず 0 か 1 に収束する！
（この本じゃなくて probabilistic methods の方に載ってる．）
Threshold functions and second moments
今度は，相変わらず大きな $n$ を考えるが，$p$ の変化によってどうなるか．今度は$p$ は定数でなく $n$ の関数．
あるところで 0 から 1 （あるいは 1 から 0）に変わる事がある．これを threshold function と呼ぶ．
- 固定した $H$ を部分グラフとして持つ
- 0 になる側：期待値から Markov's inequality
- 1 になる側：期待値は使えない．second moment & Chebyshev's inequality
- threshold function は $t(n) = n^{-1/d(H)}$
- densest subgraph $d(H) = \max_{H' \subseteq H} \frac{|E(H')|}{|V(H')|}$
Quantifying Long-Term Scientific Impact (Science 2013)
バラバシのグループ
- 論文事の非引用回数の時系列変化を予測する研究
- 引用ネットワークの入次数の変化
- （論文の価値 ＝ 引用数）
- モデル
- BA に類似
- 論文本来の魅力×優先的選択×魅力の時間的減衰
- 結果
- 凄い！全部の論文をスケールしたら全部同じ累積分布に！
