发行说明

igraph 0.6 是 igraph 的一个主要新版本。它包含许多新功能和重大更改，大量的错误修复和改进。与往常一样，我们感谢发送评论、错误报告、问题的人们，特别是为代码做出贡献的人们。

请参阅下面的主要更改列表，其中包含指向文档相关部分的链接。此处列出了 R、Python 和 C 中的新功能。

请参阅最后以获取（更）完整的更改列表。

社区检测改进

通过精确模块化优化进行社区结构检测。由于模块化优化是一个 NP 完全问题，因此这仅适用于小型图。请参阅 igraph_community_optimal_modularity。

添加了 Blondel 等人的多层模块化优化算法。请参阅 igraph_community_multilevel。

基于 Aaron Clauset 代码的层级随机图和社区发现。有关详细信息，请参见 手册。

感谢 Emmanuel Navarro 的代码，我们现在支持 InfoMAP 社区发现方法。请参阅 igraph_community_infomap。

Newman 和 Girvan 的边介数社区检测方法现在也适用于加权图。请参阅参考手册。

我们添加了一些函数来比较各种社区结构。请参阅 igraph_compare_communities。

Igraph 现在实现了 David Morton 的 Spectral Coarse Graining 方法，我们的实现基于他的代码。请参阅手册。

内聚块查找函数已从头开始用 C 重写。它们现在更快，并且具有更好的 API。请参阅 igraph_cohesive_blocks。

与中心性相关的函数

度、接近度、介数和特征向量中心性的中心化分数。请参阅手册。

个性化 PageRank 分数。请参阅手册。

权威性和枢纽分数、介数和接近度计算现在都支持边权重。请参阅手册。

杉山布局

Igraph 现在实现了用于分层有向无环图的 Sugiyama 布局算法。请参阅 igraph_layout_sugiyama。

二分图中的最大匹配

Igraph 现在实现了 push-relabel 算法和 Kuhn-Munkres 算法（也称为匈牙利方法），以查找未加权和加权二分图中的最大匹配。请参阅手册。

C 层中的新功能

• 最大基数搜索：igraph_maximum_cardinality_search() 和弦性测试：igraph_is_chordal()。
• 支持 DL 文件格式，igraph_read_graph_dl()。请参阅 http://www.analytictech.com/networks/dataentry.htm。
• 添加了具有许多回调的通用广度优先和深度优先搜索实现（igraph_bfs()、igraph_dfs()）。
• 度、接近度、介数和特征向量中心性的中心化分数，请参阅 igraph_centralization()。
• 添加了 igraph_sparsemat_t，这是一种基于 Tim Davis 的 CXSparse 库实现稀疏矩阵的类型。请参阅 http://www.cise.ufl.edu/research/sparse/CXSparse/。
• 个性化 Page-Rank 分数，igraph_personalized_pagerank() 和 igraph_personalized_pagerank_vs()。
• 分类系数，igraph_assortativity()，igraph_assortativity_nominal() 和 igraph_assortativity_degree()。
• 添加了 Blondel 等人的多层模块化优化社区结构检测算法，请参阅 igraph_community_multilevel()。
• 添加了 igraph_version() 函数。
• 星形布局：igraph_layout_star()。
• 用于计算非诱导子图的函数：igraph_subgraph_edges()。
• 两个社区结构之间的距离：igraph_compare_communities()。
• 通过精确模块化优化进行社区结构，igraph_community_optimal_community()。
• 更全面的最大流量和最小割计算，请参阅函数 igraph_maxflow()，igraph_mincut()，igraph_all_st_cuts()，igraph_all_st_mincuts()。
• 基于多维缩放的布局，igraph_layout_mds()。
• 现在可以通过 API 访问随机数生成器。可以使用来自外部来源的多个 RNG。默认的 RNG 是 MT19937。
• 添加了 igraph_get_all_shortest_paths_dijkstra，用于计算所有非负加权最短路径。
• 检查有向图是否为 DAG，igraph_is_dag()。
• 内聚块，a'la Moody & White，igraph_cohesive_blocks()。
• Igraph 函数现在可以打印状态消息，请参阅 igraph_status() 和相关函数。
• 支持写入 LEDA 文件格式，igraph_write_graph_leda()。
• 收缩顶点，igraph_contract_vertices()。
• C 参考手册现在有很多示例程序。
• 层级随机图和社区发现，移植 Aaron Clauset 的代码。请参阅 igraph_hrg_game()，igraph_hrg_fit() 等。
• igraph_has_multiple() 用于确定图是否具有多条边。
• 新布局 igraph_layout_grid() 和 igraph_layout_grid_3d()。
• igraph_integer_t 现在确实是一个整数，它曾经是一个双精度浮点数。
• igraph_minimum_spanning_tree()，调用加权或未加权实现。
• 偏心率 (igraph_eccentricity()) 和半径 (igraph_radius()) 计算。
• Minh Van Nguyen 编写的几种博弈论更新规则。请参阅 igraph_deterministic_optimal_imitation()，igraph_stochastic_imitation()，igraph_roulette_wheel_imitation()，igraph_moran_process(),
• 用于分层有向无环图的 Sugiyama 布局算法，igraph_layout_sugiyama()。
• 新图生成器：igraph_static_fitness_game()，igraph_static_power_law_game()。
• 添加了 InfoMAP 社区发现方法，感谢 Emmanuel Navarro 的代码。请参阅 igraph_community_infomap()。
• 添加了 Spectral Coarse Graining 算法，请参阅 igraph_scg()。
• 添加了一个函数来计算顶点的多样性分数，igraph_diversity()。

C 层中的重大更改

• 权威性 (igraph_authority_score()) 和枢纽 (igraph_hub_score()) 分数现在支持边权重。
• 图拉普拉斯算子计算 (igraph_laplacian()) 现在支持边权重。
• 在介数 (igraph_betweenness()) 和接近度 (igraph_closeness()) 计算中支持边权重。
• 在 VF2 图同构算法中支持顶点和边着色（igraph_isomorphic_vf2()，igraph_count_isomorphisms_vf2()，igraph_get_isomorphisms_vf2()，igraph_subisomorphic_vf2()，igraph_count_subisomorphisms_vf2()，igraph_get_subisomorphisms_vf2()）。
• 为 igraph_vector*_t，igraph_matrix*_t 和 igraph_strvector_t 类型添加了打印操作。
• 双连通分量计算 (igraph_biconnected_components()) 现在可以返回组件本身。
• 特征向量中心性计算，igraph_eigenvector_centrality() 现在适用于有向图。
• 使用 get_shortest_paths() 和 get_shortest_paths_dijkstra() 的最短路径计算现在可以返回路径上的边。
• 介数计算现在可以使用任意大的整数，这是某些格子状图形避免溢出所必需的。
• igraph_bipartite_projection() 计算边的多重性。
• igraph_barabasi_game() 已被重写，现在支持三种算法，默认算法不生成多条边或环边。
• Watts-Strogatz 图生成器 igraph_watts_strogatz() 现在可以创建没有环边的图。
• igraph 现在应该是线程安全的，在支持线程局部存储的架构上（Linux 和 Windows：是，Mac OSX：否）。

我们还修复了许多错误，太多了无法在此处包含，抱歉。您可以查看我们在 https://bugs.launchpad.net/igraph 上的错误跟踪器，以检查是否已修复错误。感谢所有报告错误的人。特别感谢 Minh Van Nguyen 提供了大量错误报告、文档修复和贡献的代码！