担当区分：研究代表者  資金種別：競争的資金

担当区分：研究分担者 

制約条件を満たす解の列挙、解の個数の数え上げ、すべての解の中からのランダムサンプリングなどのアルゴリズムの設計は、互いに深く関連しつつも、それぞれ独自の技法が必要とされることが多い。このため、それぞれのアルゴリズムは個別に設計されることが多い。本研究課題では、制約条件が定義する解空間の性質についての理解をもとに、基本的なアイデアを記述し、その記述から各アルゴリズムを統一的に導出するための基盤技術の研究を行う。

担当区分：研究代表者 

配分額：2600000円 （ 直接経費：2000000円 、 間接経費：600000円 ）

部分集合列挙の研究に対する近年の大きな進展として，部分グラフ列挙分野で2019年に近接探索（proxmity search）とよばれる技法が開発され，列挙を容易にする十分条件が明らかになった．　しかし，近接探索では，ある列挙問題を効率良く解くアルゴリズムの存在性を仮定するため，問題ごとに専用のアルゴリズムを設計する必要があるため，十分条件として扱いづらい．また，近接探索のアイディアは部分グラフ列挙問題以外にも適用可能であると申請者は考える．そこで本研究では，近接探索の他の列挙問題に対する拡張と，あるアルゴリズムの存在性を用いない効率良い列挙のための十分条件の発見を目指す．
本年度は独立性システムに関する列挙問題とマトロイドに関する列挙問題の特殊系となるグラフの列挙問題について研究を行った．
独立性システムの列挙に関しては k -拡張システムの極大解列挙アルゴリズムの構築に取り組んだ．これは定義から， k が定数であるならば多項式遅延で列挙できることがわかった．しかし，この結果の興味深い点は，多項式遅延列挙ができるが入力制約問題が多項式時間で解けるかがわかっていないという点である．そこで，次なる課題として，入力制約問題が多項式時間で解けるかを調べるために具体的な離散構造の列挙問題に取り組んだ．その問題として，マトロイドマッチングについて研究を行った．マトロイドマッチングは組合せ最適化分野で古くから知られる離散構造であり，二部グラフマッチングの一般化となっている．この問題は最適化問題としてはNP-困難であることが知られているが，列挙問題としてみた時，マトロイドマッチングの特殊系の問題は入力制約問題が多項式時間で解けることに気づいた．そこで，マトロイドマッチングについての列挙問題を研究したところ，マトロイドマッチングが2-拡張可能システムであることがわかった．この結果はグラフをハイパーグラフに拡張した場合，ハイパー辺のサイズが定数 k であればマトロイドマッチングは k-拡張可能システムになることがわかった．従って，この構造は多項式遅延で列挙できることがわかったが，まだ入力制約問題が多項式時間で解ける反例は得られなかった．
次に，マトロイドに関連するグラフ上の列挙問題としてはグラフ中の極小な全域2辺連結部分グラフを列挙する問題について研究を行い，グラフが平面的である場合はこの問題は多項式遅延が可能であると予想する．これは平面グラフにおいて，辺連携性と最小サイクルが非常に深い関係があるため，その知見を用いた良いアルゴリズムが設計できるためである．
本研究の目標は多項式遅延が容易に可能な離散構造を明らかにすることである．これを実現するため，独立性システムという抽象度の高い離散構造に着目し，入力制約問題を解く列挙アルゴリズムを用いない列挙アルゴリズムの構築を行なっている．そのための重要な離散構造の例としてk-拡張システムが存在することが明らかになり，この構造はマトロイドマッチングという組合せ最適化分野で扱われる多くの問題を一般化した離散構造を含むことがわかった．この結果から，二部グラフマッチングを一般化した多くの離散構造は容易に多項式遅延で列挙できることがわかる．これらの結果から組合せ最適化分野で古くから研究されている多くの離散構造は多項式遅延が容易なことがわかった．一方，これらの結果を進展させようとしたが， k - 拡張システムより一般の独立性システムでは多項式遅延は容易ではなく，事実，kが一般の場合は列挙アルゴリズム分野の長年の未解決問題を含む問題になってしまうことが明らかになった．そこで，今後の研究計画として，独立性システムだけではなく，他の離散構造についてもこれらの結果で得られた知見が使えないかを検討する．
今後の研究の推進方策として，まずは去年度に得られた結果をまとめて論文化することが重要である．去年度得られた結果は本研究の目的から興味深いと感じる内容だったが，技術的な貢献は少なく，現在の結果だけで論文化するには難しいと考えていた．しかし，現状 k - 拡張システムに関する良い結果を得るための明確な方針がないため，現在得られている結果までをまとめて論文化することを目指す．
これらの論文化をした後の研究として，マトロイドと関連するグラフ上の問題について研究を考えていたが，これまでの研究で，列挙アルゴリズム分野の大きな未解決問題である凸多面体の頂点列挙が部分集合列挙問題として，定式化できることに気づいた．さらに，凸多面体の頂点列挙に関しては多項式遅延ではない列挙アルゴリズムが多く，本研究で得られた知見がどの程度適用可能なのかも興味深い．このように今まで研究していたグラフや独立性システム以外の離散構造からこれまでの研究を見返すことで，容易に多項式遅延で列挙可能な離散構造の更なる発見を目指して研究を行う．この問題は一般の凸多面体の頂点列挙は長年の未解決問題で解決が困難であるため，特殊な凸多面体について扱う．具体的にはnetwork LPと呼ばれる特殊な線形制約で表現される凸多面体について扱う．この構造は効率よく列挙が可能だが，多項式遅延が可能かは未解決な問題であるため，最初の一歩の研究として適切な問題であると考える．

担当区分：研究分担者 

近年、ソーシャル・ネットワーキングサービス（以下SNS）では、デマ拡散や誹謗中傷といった非合理的かつ偶発的な群衆行動（集合行動）が頻発し、深刻な社会問題になっている。本研究では、集合行動発生時に観測されるSNS上の話題構造に注目し、多様性の低下や対立、急激な成長といった構造及びその変化をモデル化することで集合行動を可視化する。自然言語的・社会ネットワーク的な時系列データにおけるコミュニティやバーストのような局所的・大域的な構造を捉えることで、集合行動の俯瞰や検知への展開を目指す。
1. Two-Stage Clustering 手法の開発
2021年度は、SNSにおける人々の反応を分析するために、マイクロクラスタリングと時系列クラスタリングを組み合わせた Two-Stage Clustering 手法を提案し、コロナワクチンに対するTwitterデータ（全量データ）の分析を行った。この手法は、これまで内容の類似度に加えて、時系列上のパターン類似度を考慮できる効率的な手法であり、これにより、コロナワクチンに関する12M以上のTweet集合を、速報ニュースへの反応、Tweetへの反応、その他（デマなど）に分類できることを示した。結果を論文としてまとめ、BigData2021にも採択された。また招待講演等でも紹介を行った。
２. コロナワクチンに関する人々の反応評価（時系列分析）
さらにTwitterの全量データを対象として、コロナワクチンに対する人々の反応のセンチメント分析（時系列評価）にも取り組んでおり、コロナワクチンに対する日本国民の気持ちが時間とともにどのような変遷をたどったかについて考察している。結果は、近日中に社会科学系のジャーナルに投稿予定である。
3. マイクロクラスタリング手法の改良
大規模データに対応可能とするために、マイクロクラスタリング手法を、より類似度の高いインスタンスを初期のタイミングで集約する改良を行った。これにより、数千万件規模のTwitterデータが標準的なPC上でリーズナブルな速度で分析可能となった。大規模データ分析において、極めて重要な成果であると認識している。
2021年度の計画は、「SNS上で発生する集合行動の分類・整理」であったが、Two-Stage Clustering 手法により、大まかな分類、整理が出来たと考える。対象話題に対する内容の類似度（マイクロクラスタリングによる分類）に加え、時系列上のパターンの類似度でクラスタリングを行うことにより、人々の反応（集団的な行動）を速報ニュースへの反応、Tweetへの反応、その他（デマなど）に分類出来る可能性を示すことが出来た。特に時系列変化を見ることで、急激な成長や衰退を可視化することが可能となり、本テーマにおける構造変化分析の重要性が確認出来た。
また、マイクロクラスタリング手法の改良により、数千万件規模のTwitterデータが標準的なPC上でリーズナブルな速度で分析可能となった。大規模データ分析において、極めて重要な成果であると認識している。
１．Two-Stage Clustering 手法のさらなる開発
2021年度は、SNSにおける人々の反応を分析するために、マイクロクラスタリングと時系列クラスタリングを組み合わせた Two-Stage Clustering 手法を提案し、BigData2021にも採択された。この手法は、これまで内容の類似度に加えて、時系列上のパターン類似度を考慮できる効率的な手法であり、これにより、コロナワクチンに関する12M以上のTweet集合を、速報ニュースへの反応、Tweetへの反応、その他（デマなど）に分類できることを示した。2022年度は、Two-Stage Clustering 手法の効果を更に確認するために、他の話題（オリンピックや選挙など）への適応、時系列手法の精査などを行う。これにより、何らかの事象が発生したときの人々の反応分析の制度を挙げ、当初目的としている集合行動把握へとつなげていく。
<BR>
2．SNS上で発生する集合行動の分類・整理の精緻化
Two-Stage Clustering手法の分析結果を受け、SNS上でどのような集合行動が発生しているか、その際に対象話題に対してどのような構造変化が起きているかの観察・分析・整理を行い、モデル化の基礎となる概念の体系化を行う。意見の偏り、意見の対立、急激な成長といった話題の構造変化が集合行動を表現すると考え、実データによる観察を行う。また、社会科学的観点から集合行動を調査・考察し、SNS上での集合行動が誘発するであろう現象の考察と、それらの現象の実データでの検証も行う。これらを通じて、集合構造を表現する形質情報を抽出・定義する。

担当区分：研究代表者 

配分額：4810000円 （ 直接経費：3700000円 、 間接経費：1110000円 ）

列挙問題はその問題自体の効率良い計算の理論的限界の研究が行われるだけでなく，最適化や，データマイニングやデータベース分野でも盛んに研究が行われおり，理論と実用の両面から研究されている重要な問題である．しかし，既存の列挙の理論研究と実用を考えたとき，理論的に効率良い列挙アルゴリズムの研究には課題があると申請者は考える．特に申請者が考える大きな課題は，実用上の有望な解と定式化した列挙問題の解のギャップが大きすぎることである．このギャップにより，列挙した解のほぼ全てが無意味な場合もある．そのため，本研究では実用を見据えた新たな列挙問題の提案とその列挙問題を解くアルゴリズムの基盤技術開発を行う．
今年度は列挙アルゴリズムに関する3編の論文を執筆し，うち1編がデータベース分野のトップ会議であるPODS 2022に採択された．また，列挙アルゴリズムの新たな応用として，ある離散構造の重み和が重い順に上位k個を効率良く計算するアルゴリズムが存在すれば，そのアルゴリズムを用いて多様な組合せ構造を発見する効率良い近似アルゴリズムを開発した．この結果も論文化して現在国際会議に投稿中である．
列挙アルゴリズム，特に最適化制約を加えた列挙問題に対する近似的な列挙アルゴリズムについては，入力制約問題という特殊な列挙問題が解ける問題に関して，効率良い近似列挙アルゴリズムを与えた．この結果は現在アルゴリズム分野の学術雑誌であるdiscrete applied mathematicsに投稿中である．さらに，この論文で開発した技法を適用できる新たな問題も発見した．具体的には極小な連結辺支配集合が近似的に列挙できることを明らかにした．列挙において頂点に関する連結性を扱うことはしばしば困難になるため，本研究では辺に関する連結性を持つ問題に関して列挙アルゴリズムが構成できるかどうかを研究した．この結果は現在プレプリントとして公開している．
また，近似的な列挙アルゴリズムは列挙の困難性と最適化の困難性を同時に持つため，近似的な列挙アルゴリズムの研究のためには最適化制約を除いた場合の列挙の研究を深めることも重要である．そこで，本年度は極小なシュタイナー木という辺の連結性に関するグラフの構造に対し，効率良い列挙アルゴリズムの研究を行った．この構造の列挙は2000年台中盤にデータベース分野でも行われており，グラフアルゴリズム分野以外でも興味が持たれている問題である．今年度はこの問題に対して線型遅延の効率良い列挙アルゴリズムを与え，PODS 2022に採択された．
今年度は近似的な列挙に関する論文を2編の執筆と投稿，極小な部分集合に関する列挙に関する論文を1編を出版することができた．これらの結果は申請時に公開していたプレプリントの結果が元になっており，超グラフ技法で培った知見を用いて得られた結果である．また，現在プレプリントを公開中の極小な連結辺支配集合の近似的な列挙についてはCKS性を持たない，つまり入力制約問題を多項式時間で解くことができないが，多項式遅延かつ定数近似比で列挙ができることを明らかにした．
さらに，列挙アルゴリズムの応用として多様な解の発見という人工知能分野で興味が持たれている問題との関係を発見することができた．特に，このような列挙アルゴリズムが，多様な解の発見という見た目が大きく違う問題を解くため道具として有用であると示すことは，申請書にあるように，他分野への列挙応用への基盤となると考えている．
昨年度では解グラフ技法を元にする近似的な列挙アルゴリズムの開発を行なった．これらの結果は列挙アルゴリズム分野で用いられる技法だけを用いて得られた興味深い結果であると考える．しかし，近似アルゴリズムの設計技法は数多く存在し，これらのアルゴリズム設計技法から得られる知見も多いのではないかと予想する．事実，近似的な列挙とは多少問題設定は異なるが，トップ-k列挙分野においては最適化アルゴリズムと列挙アルゴリズムの両者の技法を組合せたアルゴリズム設計技法というのは一般的である．そこで，今後の研究の推進方策として，超グラフ技法による列挙アルゴリズムの研究に加え，近似アルゴリズムの技法を取り入れたアルゴリズム設計ができるかどうかを検討する．