更改

== 网络粗粒化方法 ==

== 网络粗粒化方法 ==

=== 基于最短路的方法 ===

=== 基于最短路的方法 ===

基于最短路长度定义节点间距，借助分形几何的盒覆盖思想<ref name="Mandelbrot_Fractal_Geometry">{{cite journal|author1=Mandelbrot B. B.|title=The Fractal Geometry of Nature Vol. 2|journal=Freeman|year=1982|url=}}</ref><ref name="Samsel_fractal_communities">{{cite journal|author1=Samsel M|author2=Makulski K|author3=Łepek M|author4=Fronczak A|author5=Fronczak P.|title=Towards fractal origins of the community structure in complex networks: a model-based approach|journal=Preprint at arXiv|year=2023|url=}}</ref>

采用最短路的长度定义节点间距是网络粗粒化方法之一，该方法借助分形几何中的盒覆盖思想（box-covering）<ref name="Mandelbrot_Fractal_Geometry">{{cite journal|author1=Mandelbrot B. B.|title=The Fractal Geometry of Nature Vol. 2|journal=Freeman|year=1982|url=}}</ref><ref name="Samsel_fractal_communities">{{cite journal|author1=Samsel M|author2=Makulski K|author3=Łepek M|author4=Fronczak A|author5=Fronczak P.|title=Towards fractal origins of the community structure in complex networks: a model-based approach|journal=Preprint at arXiv|year=2023|url=}}</ref>实现迭代重整化群变换。该方法以最短路距离为度规（注：数学上通常称为度量），将指定距离内的节点聚合成粗粒化节点形成更粗的空间分辨率，从而生成重整化群序列<ref name="Song_Self_similarity">{{cite journal|author1=Song C|author2=Havlin S|author3=Makse H. A.|title=Self-similarity of complex networks|journal=Nature|year=2005|volume=433|url=}}</ref>。此方法能够揭示网络的自相似性与分形特征[14,19–21]，并能给出新生长机制<ref name="Song_Origins_fractality">{{cite journal|author1=Song C|author2=Havlin S|author3=Makse H. A.|title=Origins of fractality in the growth of complex networks|journal=Nat. Phys.|year=2006|volume=2|url=}}</ref>和网络普适类分类<ref name="Radicchi_Complex_networks_renormalization">{{cite journal|author1=Radicchi F|author2=Ramasco J|author3=Barrat A|author4=Fortunato S.|title=Complex networks renormalization: flows and fixed points|journal=Phys. Rev. Lett.|year=2008|volume=101|url=}}</ref><ref name="Rozenfeld_Small_world_fractal">{{cite journal|author1=Rozenfeld H. D.|author2=Song C|author3=Makse H. A.|title=Small-world to fractal transition in complex networks: a renormalization group approach|journal=Phys. Rev. Lett.|year=2010|volume=104|url=}}</ref>。然而受限于小世界特性，以最短路为距离准则的重整化群变换难以有效解耦和揭示标度行为。因此，这类变换下度分布的自相似性并不伴随关联函数的标度律而出现，特别是在网络集聚方面，这个特征表现得更加明显。

实现迭代重整化群变换。该方法以最短路距离为度量，将指定距离内的节点聚合成粗粒化节点，生成重整化群序列<ref name="Song_Self_similarity">{{cite journal|author1=Song C|author2=Havlin S|author3=Makse H. A.|title=Self-similarity of complex networks|journal=Nature|year=2005|volume=433|url=}}</ref>，可揭示网络的自相似性与分形特征<ref name="Song_Self_similarity">{{cite journal|author1=Song C|author2=Havlin S|author3=Makse H. A.|title=Self-similarity of complex networks|journal=Nature|year=2005|volume=433|url=}}</ref><ref name="Goh_Skeleton_fractal">{{cite journal|author1=Goh K.-I|author2=Salvi G|author3=Kahng B|author4=Kim D.|title=Skeleton and fractal scaling in complex networks|journal=Phys. Rev. Lett.|year=2006|volume=96|url=}}</ref><ref name="Kim_Fractality_self_similarity">{{cite journal|author1=Kim J. S|author2=Goh K.-I|author3=Kahng B|author4=Kim D.|title=Fractality and self-similarity in scale-free networks|journal=New J. Phys.|year=2007|volume=9|url=}}</ref><ref name="Fronczak_Scaling_theory">{{cite journal|author1=Fronczak A.|title=Scaling theory of fractal complex networks|journal=Sci. Rep.|year=2024|url=}}</ref>

，并用于新生长机制<ref name="Song_Origins_fractality">{{cite journal|author1=Song C|author2=Havlin S|author3=Makse H. A.|title=Origins of fractality in the growth of complex networks|journal=Nat. Phys.|year=2006|volume=2|url=}}</ref>和网络普适类分类<ref name="Radicchi_Complex_networks_renormalization">{{cite journal|author1=Radicchi F|author2=Ramasco J|author3=Barrat A|author4=Fortunato S.|title=Complex networks renormalization: flows and fixed points|journal=Phys. Rev. Lett.|year=2008|volume=101|url=}}</ref><ref name="Rozenfeld_Small_world_fractal">{{cite journal|author1=Rozenfeld H. D.|author2=Song C|author3=Makse H. A.|title=Small-world to fractal transition in complex networks: a renormalization group approach|journal=Phys. Rev. Lett.|year=2010|volume=104|url=}}</ref>。但受小世界特性限制，该方法难以有效解耦和揭示标度行为，度分布自相似性不伴随关联函数标度律，尤其在网络集聚方面。

研究者还提出在规则格点网络添加长程连接实现实空间重整化群变换，用于研究Watts-Strogatz模型临界点行为<ref name="Newman_Watts_RG_small_world">{{cite journal|author1=Newman M|author2=Watts D.|title=Renormalization group analysis of the small-world network model|journal=Phys. Lett. A|year=1999|volume=263|url=}}</ref>和格点无标度网络模型<ref name="Kim_Geographical_coarse_graining">{{cite journal|author1=Kim B. J.|title=Geographical coarse graining of complex networks|journal=Phys. Rev. Lett.|year=2004|volume=93|url=}}</ref>，但需预知节点坐标或区分短程与长程连接，而真实网络中此类信息常未知。

另一方面，研究者提出，可以在具有短程连接性质的规则格点网络中添加长程连接，进而实现实空间重整化群变换。这类变换已用于研究若干问题，包括Watts-Strogatz模型在临界点附近的行为（在最短路密度趋于零的极限情形<ref name="Newman_Watts_RG_small_world">{{cite journal|author1=Newman M|author2=Watts D.|title=Renormalization group analysis of the small-world network model|journal=Phys. Lett. A|year=1999|volume=263|url=}}</ref>）以及经变换其拓扑性质保持不变的格点上的无标度网络模型<ref name="Kim_Geographical_coarse_graining">{{cite journal|author1=Kim B. J.|title=Geographical coarse graining of complex networks|journal=Phys. Rev. Lett.|year=2004|volume=93|url=}}</ref>。然而，这些方法需预知节点坐标，或需明确区分短程连接（定义实际参与粗粒化的路径长度）与长程连接。对于真实网络，这类信息通常未知甚至无法明确定义。

=== 谱方法 ===

=== 谱方法 ===

基于网络谱性质的方法通过保持特定过程动力学行为进行粗粒化。谱粗粒化最初用于研究网络随机游走，保留随机矩阵最大特征值及对应特征向量以保持大尺度行为，剔除快模态同时保留慢模态<ref name="Gfeller_Spectral_coarse_graining">{{cite journal|author1=Gfeller D|author2=Los Rios P.|title=Spectral coarse graining of complex networks|journal=Phys. Rev. Lett.|year=2007|volume=99|url=}}</ref>，已推广至二部网络<ref name="Wang_Spectral_coarse_graining_bipartite">{{cite journal|author1=Wang Y|author2=Zeng A|author3=Di Z|author4=Fan Y.|title=Spectral coarse graining for random walks in bipartite networks|journal=Chaos|year=2013|volume=23|url=}}</ref>和耦合振子同步动力学研究<ref name="Gfeller_Spectral_synchronization">{{cite journal|author1=Gfeller D|author2=Los Rios P.|title=Spectral coarse graining and synchronization in oscillator networks|journal=Phys. Rev. Lett.|year=2008|volume=100|url=}}</ref><ref name="Chen_Spectral_coarse_graining_clustered">{{cite journal|author1=Chen J|author2=an Lu J|author3=Lu X|author4=Wu X|author5=Chen G.|title=Spectral coarse graining of complex clustered networks|journal=Commun. Nonlinear Sci. Numer. Simul.|year=2013|volume=18|url=}}</ref><ref name="Jia_Optimization_algorithms_SCG">{{cite journal|author1=Jia Z|author2=Zeng L|author3=Wang Y.-Y.|author4=Wang P.|title=Optimization algorithms for spectral coarse-graining of complex networks|journal=Physica A|year=2019|volume=514|url=}}</ref>，也用于有向网络同步<ref name="Zeng_Coarse_graining_synchronization">{{cite journal|author1=Zeng A|author2=Lü L.|title=Coarse graining for synchronization in directed networks|journal=Phys. Rev. E|year=2011|volume=83|url=}}</ref>和可控性分析<ref name="Wang_Spectral_controllability">{{cite journal|author1=Wang P|author2=Xu S.|title=Spectral coarse grained controllability of complex networks|journal=Physica A|year=2017|volume=478|url=}}</ref>。

另一种方法基于网络的谱性质，该类方法通过保持特定过程的动力学行为的方式进行粗粒化处理。谱粗粒化方法最初是为研究网络上的随机游走而设计的，其通过保留随机矩阵的最大特征值及对应特征向量来确保大尺度行为的保持，在有效剔除快模态的同时保持慢模态不变<ref name="Gfeller_Spectral_coarse_graining">{{cite journal|author1=Gfeller D|author2=Los Rios P.|title=Spectral coarse graining of complex networks|journal=Phys. Rev. Lett.|year=2007|volume=99|url=}}</ref>。该方法已推广至二部网络（bipartite networks）<ref name="Wang_Spectral_coarse_graining_bipartite">{{cite journal|author1=Wang Y|author2=Zeng A|author3=Di Z|author4=Fan Y.|title=Spectral coarse graining for random walks in bipartite networks|journal=Chaos|year=2013|volume=23|url=}}</ref>，并已用于耦合振子的同步动力学研究中，此时网络的拉普拉斯矩阵成为这一方法的核心算符（注：“算符”在数学上通常称为“算子”）<ref name="Gfeller_Spectral_synchronization">{{cite journal|author1=Gfeller D|author2=Los Rios P.|title=Spectral coarse graining and synchronization in oscillator networks|journal=Phys. Rev. Lett.|year=2008|volume=100|url=}}</ref><ref name="Chen_Spectral_coarse_graining_clustered">{{cite journal|author1=Chen J|author2=an Lu J|author3=Lu X|author4=Wu X|author5=Chen G.|title=Spectral coarse graining of complex clustered networks|journal=Commun. Nonlinear Sci. Numer. Simul.|year=2013|volume=18|url=}}</ref><ref name="Jia_Optimization_algorithms_SCG">{{cite journal|author1=Jia Z|author2=Zeng L|author3=Wang Y.-Y.|author4=Wang P.|title=Optimization algorithms for spectral coarse-graining of complex networks|journal=Physica A|year=2019|volume=514|url=}}</ref>。类似的谱粗粒化思想也可以用于有向网络的同步<ref name="Zeng_Coarse_graining_synchronization">{{cite journal|author1=Zeng A|author2=Lü L.|title=Coarse graining for synchronization in directed networks|journal=Phys. Rev. E|year=2011|volume=83|url=}}</ref>和可控性分析<ref name="Wang_Spectral_controllability">{{cite journal|author1=Wang P|author2=Xu S.|title=Spectral coarse grained controllability of complex networks|journal=Physica A|year=2017|volume=478|url=}}</ref>等研究。使用图的拉普拉斯矩阵的特征向量与特征值，研究者进一步利用确定性多层网络（如高斯模型的Cayley树和钻石晶格<ref name="Aygün_Spectral_RG_networks">{{cite journal|author1=Aygün E|author2=Erzan A.|title=Spectral renormalization group theory on networks|journal=J. Phys. Conf. Ser.|year=2011|volume=319|url=}}</ref><ref name="Tuncer_Spectral_RG_Gaussian">{{cite journal|author1=Tuncer A|author2=Erzan A.|title=Spectral renormalization group for the Gaussian model and \$Psi\$4 theory on nonspatial networks|journal=Phys. Rev. E|year=2015|volume=92|url=}}</ref>）探索了场论重整化群方法对处理有序-无序现象的可能性<ref name="Aygün_Spectral_RG_networks">{{cite journal|author1=Aygün E|author2=Erzan A.|title=Spectral renormalization group theory on networks|journal=J. Phys. Conf. Ser.|year=2011|volume=319|url=}}</ref>。这些研究为建立基于拉普拉斯谱的图重整化理论框架<ref name="Villegas_Laplacian_RG">{{cite journal|author1=Villegas P|author2=Gili T|author3=Caldarelli G|author4=Gabrielli A.|title=Laplacian renormalization group for heterogeneous networks|journal=Nat. Phys.|year=2023|volume=19|url=}}</ref>奠定了基础，本文后续将对此设立独立章节进行详细讨论。

=== 拓扑方法 ===

=== 拓扑方法 ===

基于拓扑性质的粗粒化方法包括节点中心性度量（如度<ref name="Chen_Statistically_consistent_CG">{{cite journal|author1=Chen H|author2=Hou Z|author3=Xin H|author4=Yan Y.|title=Statistically consistent coarse-grained simulations for critical phenomena in complex networks|journal=Phys. Rev. E|year=2010|volume=82|url=}}</ref>和广义度<ref name="Long_Generalized_degree_CG">{{cite journal|author1=Long Y.-S|author2=Jia Z|author3=Wang Y.-Y.|title=Coarse graining method based on generalized degree in complex network|journal=Physica A|year=2018|volume=505|url=}}</ref>）、基于邻居重叠的节点相似性度量<ref name="Wang_Node_similarity_CG">{{cite journal|author1=Wang Y.|title=Coarse graining method based on node similarity in complex network|journal=Commun. Netw.|year=2018|volume=10|url=}}</ref>，以及网络模体分析<ref name="Itzkovitz_Self_dissimilarity">{{cite journal|author1=Itzkovitz S.|title=Coarse-graining and self-dissimilarity of complex networks|journal=Phys. Rev. E|year=2005|volume=71|url=}}</ref>等。

与上述方法并行发展的，是基于拓扑性质的粗粒化方法。这类技术包括：节点中心性度量（如度<ref name="Chen_Statistically_consistent_CG">{{cite journal|author1=Chen H|author2=Hou Z|author3=Xin H|author4=Yan Y.|title=Statistically consistent coarse-grained simulations for critical phenomena in complex networks|journal=Phys. Rev. E|year=2010|volume=82|url=}}</ref>和广义度<ref name="Long_Generalized_degree_CG">{{cite journal|author1=Long Y.-S|author2=Jia Z|author3=Wang Y.-Y.|title=Coarse graining method based on generalized degree in complex network|journal=Physica A|year=2018|volume=505|url=}}</ref>）、基于邻居重叠的节点相似性度量<ref name="Wang_Node_similarity_CG">{{cite journal|author1=Wang Y.|title=Coarse graining method based on node similarity in complex network|journal=Commun. Netw.|year=2018|volume=10|url=}}</ref>，这包括传统的社交网络中的结构等效节点<ref name="Lorrain_Structural_equivalence">{{cite journal|author1=Lorrain F|author2=White H. C.|title=Structural equivalence of individuals in social networks|journal=J. Math. Sociol.|year=1971|volume=1|url=}}</ref>、食物网中的营养等效物种<ref name="Dunne_Food_webs">{{cite journal|author1=Dunne J. A.|title=Food webs|journal=Encyclopedia of Complexity and Systems Science|year=2009|pages=3661–3682|url=}}</ref>的概念等）、以及作为反复重现的模式的网络模体分析<ref name="Itzkovitz_Self_dissimilarity">{{cite journal|author1=Itzkovitz S.|title=Coarse-graining and self-dissimilarity of complex networks|journal=Phys. Rev. E|year=2005|volume=71|url=}}</ref>等。

值得关注的方法包括基于度阈值的重整化<ref name="Serrano_Self_similarity_hidden_metric">{{cite journal|author1=Serrano M. Á.|author2=Krioukov D|author3=Boguñá M.|title=Self-similarity of complex networks and hidden metric spaces|journal=Phys. Rev. Lett.|year=2008|volume=100|url=}}</ref>和k核分解<ref name="Alvarez-Hamelin_K_core_decomposition">{{cite journal|author1=Alvarez-Hamelin J|author2=Dall'Asta L|author3=Barrat A|author4=Vespignani A.|title=K-core decomposition of Internet graphs: hierarchies, self-similarity and measurement biases|journal=Netw. Heterog. Media|year=2008|volume=3|url=}}</ref>。前者通过移除度低于阈值的节点定义嵌套子图层级结构，后者将网络分解为满足最小度约束的极大子图，有效揭示真实系统中超越度分布标度不变性的层级自相似性，如聚类谱的标度律。

此外，研究者还提出了基于多尺度社区检测中模块化概念的策略<ref name="Lambiotte_Multi_scale_modularity">{{cite journal|author1=Lambiotte R.|title=Multi-scale modularity in complex networks|journal=8th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks|year=2010|pages=546–553|url=}}</ref>，其思路类似于计算机科学中的多层图划分算法。这类算法包含基于节点或边属性的粗粒化启发式方法，例如针对连接均匀分布的图的重边启发式算法，通过合并具有大权值连接的节点实现粗粒化<ref name="Karypis_Multilevel_partitioning">{{cite journal|author1=Karypis G|author2=Kumar V.|title=A fast and high quality multilevel scheme for partitioning irregular graphs|journal=SIAM J. Sci. Comput.|year=1998|volume=20|url=}}</ref>。对于具有度分布呈幂律的图，也可以使用基于社区的粗粒化方案，将高度互连的顶点集合并<ref name="Abou-Rjeili_Power_law_partitioning">{{cite journal|author1=Abou-Rjeili A|author2=Karypis G.|title=Multilevel algorithms for partitioning power-law graphs|journal=Proc. 20th IEEE International Parallel & Distributed Processing Symposium|year=2006|url=}}</ref>。

=== 对称方法 ===

=== 对称方法 ===