Segarkan buku Jaringan Kompleks Pertambangan – Beragampengetahuan

Oleh: Blog Bogumił Kamiński

Repost dari:

Dua tahun lalu dengan Paweł Prałat dan François Théberge
kami menulis buku Jaringan Penambangan Kompleks.
Karena mendapat tanggapan positif dari masyarakat
Kami memutuskan untuk mulai merencanakan edisi kedua, di mana
Kami ingin menambahkan materi yang mencakup kemajuan terkini di bidang ini.

Keputusan ini mendorong saya untuk menulis sesuatu tentang analisis grafik
yang juga merupakan aplikasi bahasa Julia yang bagus.

Posting ditulis di bawah Julia 1.9.0 dan Graphs.jl 1.8.0.

Mari saya mulai dengan skenario bisnis.
Katakanlah Anda memiliki satu set produk di toko dan mengetahui set yang mana
dibeli bersama. Anda mewakili data ini sebagai grafik di mana
Node adalah produk dan ujungnya mewakili pembelian bersama produk.

Anda ingin mencari produk yang tidak dibeli bersamaan, tapi itu
jatuh ke dalam keranjang yang sama. Misalnya, katakanlah Anda memiliki dua jenis
susu. Kemungkinan besar mereka tidak dibeli bersama, tetapi keduanya
membeli dengan misalnya roti. Produk semacam itu bisa disebut pengganti.

Dalam buku tersebut, kami membahas beberapa metode lanjutan yang dapat digunakan untuk tugas ini.
Dalam posting ini, izinkan saya fokus pada cara sederhana untuk mendeteksi produk semacam itu.

Asumsikan saya memiliki empat produk i, j, kDan l. Jika di
grafik kita memiliki tepi i-j, j-k, k-lDan l-itapi tidak ada
tepian i-k Dan j-l maka kita dapat mengatakan bahwa i Dan k merupakan produk pengganti
Dan j Dan l adalah pengganti (jadi keempat tombol ini bisa dipanggil
substitusi ganda).

Dari perspektif teori graf, himpunan node {i, j, k, l} membentuk sebuah
siklus memiliki panjang 4 dan mereka tidak membentuk siklus semacam apa pun
(jadi siklus ini memiliki a lubang di dalamnya). Mari kita sebut siklus seperti itu minimal.
Kita dapat membayangkan situasi ini sebagai berikut:

Misi kami hari ini adalah sebagai berikut. Misalkan kita memiliki histogram acak
dengan n persimpangan. Dalam grafik ini, setiap sisi disertakan dengan probabilitas
p, yang tidak bergantung pada semua sisi lainnya. Kami ingin memeriksa caranya
ini berisi lebih dari 4 siklus min.

Untuk histogram stokastik, dimungkinkan untuk menghitung kuantitas yang diharapkan
minimal 4 siklus relatif mudah.

Menggunakan aditif harapan, kita dapat fokus pada empat faktor
subset dari himpunan node. Untuk setiap subset tersebut {i, j, k, l}
kami memiliki tiga kemungkinan sehingga mereka dapat membentuk 4 siklus minimum:

  i        i        i
 / \      / \      / \
l   j    l   k    k   j
 \ /      \ /      \ /
  k        j        l

Perhatikan bahwa kemungkinan mengamati salah satu dari mereka adalah p^4*(1-p)^2
(kita melihat 4 sisi dan bukan 2 sisi).

Oleh karena itu, kita dapat dengan mudah menulis sebuah fungsi yang menghitung ekspektasi
Banyaknya motif seperti :

expected_count_empty_4cycle(n, p) = p^4*(1-p)^2 * 3 * binomial(n, 4)

Mari kita hitung jumlah yang diharapkan dari sprite tersebut n setara dengan 10
Dan 100 Dan p setara dengan 0.1 Dan 0.2:

julia> expected_count_empty_4cycle.([10, 100], [0.1 0.2 0.3])
2×3 Matrix{Float64}:
   0.05103      0.64512      2.50047
 952.858    12046.0      46690.0

Fungsi bekerja dengan cepat dan baik, tetapi bagaimana jika kita membuat kesalahan dalam mendefinisikannya?
Dengan Julia, mudah menjalankan simulasi yang memeriksa hasilnya.

Mari kita mulai dengan solusi regenerasi pikiran yang biasa kita peroleh
Hasil analisis kami:

function naive_count_empty_4cycle(g)
    empty4cycle = 0
    for i in 1:nv(g), j in i+1:nv(g), k in j+1:nv(g), l in k+1:nv(g)
        empty4cycle += has_edge(g, i, j) && has_edge(g, j, k) &&
                       has_edge(g, k, l) && has_edge(g, l, i) &&
                       !has_edge(g, i, k) && !has_edge(g, j, l)
        empty4cycle += has_edge(g, i, k) && has_edge(g, k, j) &&
                       has_edge(g, j, l) && has_edge(g, l, i) &&
                       !has_edge(g, i, j) && !has_edge(g, k, l)
        empty4cycle += has_edge(g, i, j) && has_edge(g, j, l) &&
                       has_edge(g, l, k) && has_edge(g, k, i) &&
                       !has_edge(g, i, l) && !has_edge(g, j, k)
    end
    return empty4cycle
end

Fungsi tersebut diharapkan untuk mendapatkan Graphs.jl .graph g dan melewati itu semua
subset dari node-nya.

Mari kita mengujinya:

julia> using Graphs

julia> using Random

julia> using Statistics

julia> Random.seed!(1234);

julia> [mean(naive_count_empty_4cycle(erdos_renyi(10, p)) for i in 1:1000)
        for p in [0.1, 0.2, 0.3]]
3-element Vector{Float64}:
 0.051
 0.598
 2.455

Jadi hasilnya terlihat bagus untuk n=10. Tapi bagaimana dengan n=100?

Mari kita periksa waktu lari:

julia> @time naive_count_empty_4cycle(erdos_renyi(100, 0.1));
  0.142410 seconds (274 allocations: 38.594 KiB)

Kita dapat melihat bahwa fungsi ini lambat. Jika kami ingin menjalankannya 1000 kali, kami akan kalah
lebih dari 2 menit. Mari kita pikirkan pendekatan yang lebih cepat.

Ide yang bisa kita gunakan adalah sebagai berikut. Pertimbangkan dua tombol i Dan j dan menganggap mereka
Tidak terhubung. Maka cukup untuk menemukan tetangga yang sama i Dan j
dan periksa berapa banyak pasangan yang tidak terhubung.

Berikut adalah contoh implementasi dari ide ini:

function find_common_sorted!(common, ni, nj)
    empty!(common)
    iidx = 1
    jidx = 1
    while iidx <= length(ni) && jidx <= length(nj)
        if ni[iidx] < nj[jidx]
            iidx += 1
        elseif ni[iidx] > nj[jidx]
            jidx += 1
        else
            push!(common, ni[iidx])
            iidx += 1
            jidx += 1
        end
    end
    nothing
end

function fast_count_empty_4cycle(g)
    common = Int[]
    empty4cycle = 0

    for i in 1:nv(g)
        ni = neighbors(g, i)
        for j in i+1:nv(g)
            has_edge(g, i, j) && continue
            nj = neighbors(g, j)
            find_common_sorted!(common, ni, nj)
            for a in 1:length(common), b in a+1:length(common)
                empty4cycle += !has_edge(g, common[a], common[b])
            end
        end
    end
    @assert iseven(empty4cycle)
    return empty4cycle ÷ 2
end

Perhatikan bahwa dalam kode kami membagi jumlah siklus bebas yang ditemukan dengan dua yaitu
dengan asumsi bahwa node {i, j, k, l} membentuk siklus kosong, kita hitung dua kali
(sekali dimulai dengan {i, k} pasangan dan sekali mulai dengan {j, l} pasangan).

Mari kita uji fungsi kita:

julia> @time fast_count_empty_4cycle(erdos_renyi(100, 0.1));
  0.001491 seconds (280 allocations: 40.047 KiB)

Memang secara signifikan lebih cepat. Jadi kita bisa menggunakannya untuk memeriksa n=100 kasus:

julia> [mean(fast_count_empty_4cycle(erdos_renyi(10, p)) for i in 1:1000)
        for p in [0.1, 0.2, 0.3]]
3-element Vector{Float64}:
 0.051
 0.598
 2.455

julia> [mean(fast_count_empty_4cycle(erdos_renyi(100, p)) for i in 1:1000)
        for p in [0.1, 0.2, 0.3]]
3-element Vector{Float64}:
   954.364
 12017.067
 46574.827

Hasil yang diperoleh mengkonfirmasi solusi analitik kami, sehingga kami lebih percaya diri
bahwa kita benar-benar menggambarnya dengan benar.

Saya harap Anda menemukan masalah menemukan jumlah cincin minimum yang menarik.
Secara pribadi, saya sangat suka mengkodekannya di Julia. Dari catatan khusus adalah bahwa di Julia
dengan versi kode kami yang lebih cepat, kami hampir tidak melakukan alokasi apa pun:

julia> gr = erdos_renyi(1000, 0.1); @time fast_count_empty_4cycle(gr)
  2.534875 seconds (4 allocations: 496 bytes)
10169170

julia> expected_count_empty_4cycle.(1000, 0.1)
1.0064361314250002e7

dan kode berjalan cukup cepat.

Terkait