Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Tìm kiếm cấu trúc cộng đồng trong các mạng phức tạp bằng phương pháp tối ưu hóa số nguyên hỗn hợp
Tóm tắt
Việc phát hiện cấu trúc cộng đồng đã được sử dụng để tiết lộ mối quan hệ giữa các đối tượng cá nhân và sự phân nhóm của chúng trong các mạng. Bài báo này trình bày một phương pháp lập trình toán học để xác định các cấu trúc cộng đồng tối ưu trong các mạng phức tạp dựa trên việc tối đa hóa một chỉ số tính linh hoạt của mạng để phân chia mạng thành các mô-đun. Vấn đề tổng thể được lập thành mô hình lập trình bậc hai với số nguyên hỗn hợp (MIQP), có thể được giải quyết tới độ tối ưu toàn cầu bằng phần mềm tối ưu hóa tiêu chuẩn. Quy trình giải quyết được cải thiện thêm bằng cách phát triển các ràng buộc phá vỡ đối xứng đặc biệt để loại bỏ các giải pháp tương đương. Bài báo cho thấy rằng các tính năng bổ sung như kích thước mô-đun tối thiểu/tối đa và sự cân bằng giữa các mô-đun có thể dễ dàng được tích hợp vào mô hình. Tính khả thi của phương pháp tối ưu hóa được đề xuất được chứng minh qua bốn ví dụ. Các kết quả so sánh với các phương pháp khác từ tài liệu cho thấy rằng phương pháp được đề xuất có hiệu suất vượt trội trong khi đảm bảo độ tối ưu toàn cầu.
Từ khóa
#cấu trúc cộng đồng #mạng phức tạp #tối ưu hóa số nguyên hỗn hợp #lập trình toán học #tính linh hoạt của mạngTài liệu tham khảo
A. Barabasi, R. Albert, Science 286, 509 (1999)
M.E.J. Newman, SIAM Rev. 45, 167 (2003)
S. Boccaletti, V. Latora, Y, Moreno, M. Chavez, D.-U. Hwang, Phys. Rep. 424, 175 (2006)
G.W. Flake, S.R. Lawrence, C.L. Giles, F.M. Coetzee, IEEE Comput. 35, 66 (2002)
J.P. Eckmann, E. Moses, Proc. Natl. Acad. Sci. U.S.A. 99, 5825 (2002)
M. Girvan, M.E.J. Newman, Proc. Natl. Acad. Sci. U.S.A. 99, 7821 (2002)
R. Guimera, L. Danon, A.D. Guilera, F. Giralt, A. Arenas, Phys. Rev. E 68, 065103 (2003)
R. Guimera, L.A.N. Amaral, Nature 433, 895 (2005)
P. Holme, M. Huss, H. Jeong, Bioinformatics 19, 532 (2003)
M.R. Garey, D.S. Johnson, Computers and intractability, A Guide to the theory of NP-completeness (W.H. Freeman, San Francisco, 1979)
D. Fisher, J. Artif. Intell. Res. 4, 147 (1996)
M.E.J. Newman, Eur. Phys. J. B 38, 321 (2004)
S. Boettcher, A.G. Percus, Phys. Rev. E 64, 026114 (2001)
B.W. Kernighan, S. Lin, Bell Syst. Tech. J. 49, 291 (1970)
A. Pothen, H. Simon, K.P. Liou, SIAM J. Matrix. Anal. A 11, 430 (1990)
M. Gustafsson, M. Hornquist, A. Lombardi, Physica A 367, 559 (2006)
A.W. Rives, T. Galitski, Proc. Natl. Acad. Sci. U.S.A. 100, 1128 (2003)
C.V. Mering, E.M. Zdobnov, S. Tsoka, F.D. Ciccarelli, J.B. Pereira-Leal, C.A. Ouzounis, P. Bork, Proc. Natl. Acad. Sci. U.S.A. 100, 15428 (2003)
F. Radicchi, C. Castellano, F. Cecconi, V. Loreto, D. Parisi, Proc. Natl. Acad. Sci. U.S.A. 101, 2658 (2004)
C. Castellano, F. Cecconi, V. Loreto, D. Parisi, F. Radicchi, Eur. Phys. J. B 38, 311 (2004)
F.Wu, B.A. Huberman, Eur. Phys. J. B 38, 331 (2004)
J. Reichardt, S. Bornholdt, Phys. Rev. Lett. 93, 218701 (2004)
S.W. Son, H. Jeong, J.D. Noh, Eur. Phys. J. B 50, 431 (2006)
M.E.J. Newman, M. Girvan, Phys. Rev. E 69, 026113 (2004)
M.E.J. Newman, Phys. Rev. E 69, 066133 (2004)
A. Clauset, M.E.J. Newman, C. Moore, Phys. Rev. E 70, 066111 (2004)
M.E.J. Newman, Proc. Natl. Acad. Sci. U.S.A. 103, 8577 (2006)
A. Medus, G. Acuna, C.O. Dorso, Physica A 358, 593 (2005)
J. Duch, A. Arenas, Phys. Rev. E 72, 027104 (2005)
S. Fortunato, M. Barthelemy, Proc. Natl. Acad. Sci. U.S.A. 104, 36 (2007)
J.M. Kumpula, J. Saramaki, K. Kaski, J. Kertesz, Eur. Phys. J. B 56, 41 (2007)
A. Arenas, A. Fernandez, S. Gomez, e-print arXiv:physics/0703218 (2007)
G. Klein, J.E. Aronson, Nav. Res. Log. 38, 447 (1991)
Ilog, ILOG CPLEX 10.0 User's Manual (2006)
C.A. Floudas, Nonlinear and Mixed-Integer Optimisation (Oxford University Press, New York, 1995)
A. Brooke, D. Kendrick, A. Meeraus, R. Raman, GAMS: A user's guide (GAMS development Corp. Washington, DC. 1998)
W.W. Zachary, J. Anthropol. Res. 33, 452 (1977)
D. Lusseau, Proc. R. Soc. London. Ser. B (Suppl.) 270, S186 (2003)
D. Lusseau, Behav. Ecol. Sociobiol. 54, 396 (2003)
D.E. Knuth, The Stanford graphbase: a platform for combinatorial computing (Addison-Wesley, Reading, MA, 1993)
L. Dartnell, E. Simeonidis, M. Hubank, S. Tsoka, I.D.L. Bogle, L.G. Papageorgriou, FEBS. Lett. 579, 3037 (2005)
L. Danon, A. Diaz-Guilera, J. Duch, A. Arenas, J. Stat. Mech. P09008 (2005)