問題タブ [adjacency-matrix]

隣接行列を使用して、視覚的に次のように解釈できる友人のネットワークを表現しています。

このマトリックスを使用して、ユーザー1がユーザー2と友達であり、ユーザー2がユーザー3と友達であるという条件で、考えられるすべての友情の三角形のリストを作成します。私のリストでは、ユーザー1がと友達である必要はありません。ユーザー3。

小さな三角形でうまく機能するコードが少しありますが、非常に大きなスパース行列に合わせてスケーリングする必要があります。

私は約21分でcsr_matrixでコードを実行することができました。マトリックスは1032570x1032570で、88910個の格納された要素が含まれていました。合計2178893個のトリプレットが生成されました。

9428596の格納された要素を持つ1968654x1968654のスパース行列で同様のことを実行できる必要があります。

私はPythonに非常に慣れておらず（1か月弱の経験）、線形代数が得意ではありません。そのため、私のコードは行列演算を利用していません。誰かが改善のための提案をしたり、私の目的が現実的であるかどうかを教えてもらえますか？

だから私はこれに何時間も取り組んできました、そして私は非常にイライラしています。何が間違っているのかわかりません。

ダイクストラのアルゴリズムを使用して、ソース頂点と隣接行列を使用する他の4つの頂点の間の最短経路を見つけています。この背後にある考え方は、5つの都市とそれらを行き来するフライトがあり、乗り継ぎを考慮して、最も安いチケット価格を見つける必要があるということです。

私は、擬似コードである私の本のアルゴリズムと、次のWebサイトのコードに従っています：http：//vinodcse.wordpress.com/2006/05/19/code-for-dijkstras-algorithm-in- c-2 /

私が抱えている問題は、Webサイトのネストされたforループで、カウンターiが1から始まることです。これが、ソース頂点からすべての頂点までの距離が正しい理由であると考えています。 999で変更されていません。

例：

現在の距離：999220 0115130

前任者：0 3 0 2 2

ソース頂点を変更した場合でも、変更されていない最初の距離を除いて、これらの距離はすべて正しいです。

カウンターiを0に変更すると、距離ごとに混乱します。

現在の距離：0 105 0 0 0

とにかく、助けてください。関連するコードは次のとおりです。

サイズの異なる有向グラフの隣接行列を作成しました。約 30,000 の行列があり、それぞれが別のテキスト ファイルにあります。それらをどのようにクラスター化できますか、利用可能なツールはありますか。クラスタリング用の有向グラフを表す最良の方法は何ですか?

ありがとうございました。

BFS が O(m+n) である方法を理解しようとしています。ここで、n は頂点の数、m はエッジの数です。

アルゴリズムは次のとおりです。

隣接リストでは、頂点を配列/ハッシュ テーブルに格納し、各頂点が他の頂点と形成するエッジのリンク リストを格納します。

私の主な質問はこれです: get unvisited child node をどのように実装しますか? ノードを訪問済みとしてマークすることは明らかですが、トラバースするときに、リンクされたすべてのリストを通過するため、すべてのエッジを 2 回カウントするため、複雑さは O(2m+n) ですよね? それはO（m + n）に切り捨てられますか？

また、隣接行列に同様の戦略を採用できますか? サイズ nxn の行列が与えられ、特定の要素が存在するかどうかを知りたい場合、それを把握するために BFS を実行できますか?

ありがとう。

Xは、等しいサイズ（500要素）のビットベクトルを含むテキストファイルです100000（つまり、各行は500要素のベクトルです）。以下のコードを使用して隣接行列（100000 X 100000）を生成していますが、最適化されておらず、非常に時間がかかります。どうすればそれを改善できますか。

ありがとうございました。

Neo4jでグラフの隣接行列を取得することは可能ですか? それとも、自分で構築する必要がありますか?

ありがとう！

これは、クラスカルのアルゴリズムに使用した擬似コードです。ここで使用したデータ構造は隣接行列です。私は成長の順序を取得しましたn^2。正しいかどうか知りたいです。

行列のトレースを 3 乗と 4 乗で計算する必要があり、可能な限り高速である必要があります。

ここでの行列は単純なグラフの隣接行列であるため、正方対称であり、そのエントリは常に 1 または 0 であり、対角要素は常に 0 です。

行列の 2 乗へのトレースの最適化は自明です。

• トレースには対角線のエントリ (i,i) のみが必要で、他はすべてスキップします
• 行列は対称であるため、これらのエントリは i 番目の行のエントリを 2 乗して合計したものにすぎません。
• エントリは 1 または 0 であるため、二乗演算はスキップできます。

ウィキペディアで見つけた別のアイデアは、アダマール積のすべての要素、つまりエントリごとの乗算を要約することでしたが、この方法を 3 と 4 の累乗に拡張する方法がわかりません。

http://en.wikipedia.org/wiki/Trace_(linear_algebra)#Propertiesを参照してください。

盲目なだけかもしれませんが、簡単な解決策が思いつきません。

最終的には C++ の実装が必要ですが、それは質問にとって重要ではないと思います。

助けてくれてありがとう。

重み付き有向グラフのエッジを表すトライアド（vertex1、vertex2、weight）のリストがあります。プロトタイプの実装はMatlabで行われているため、これらはNx3行列としてインポートされます。ここでNはエッジの数です。したがって、これの素朴な実装は

トリブルの問題は、「id1」と「id2」が連続していないことです。それらはコードです。これは私に3つの問題を与えます。（1）「ファントム」のスプリアス頂点が多すぎる巨大な行列。これにより、その行列で使用するアルゴリズムの結果が歪められます。（2）上記のアルゴリズムの結果でコードを復元する必要があります（これは、連続する1：mのIDコードの場合は些細なことです）。

Matlabでの回答が望ましいですが、他の言語での回答からハックバックできると思います（「Rにはこれを行うライブラリがあります」という種類の事前にパッケージ化されたソリューションでない限り）。

StackOverflowは初めてですが、コミュニティに有意義な貢献をしたいと思っています。とりあえず、よろしくお願いします！

編集：複数の頂点の原点に頂点がない場合、これは解決策になります。（これは、エッジの原点のリストとIDのリストが1：1で一致することを意味します）