社区发现算法——KL算法
2022/2/4 11:45:22
本文主要是介绍社区发现算法——KL算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
K-L(Kernighan-Lin)算法
原始论文(An efficient heuristic procedure for partitioning graphs)
K-L(Kernighan-Lin)算法是一种将已知网络划分为已知大小的两个社区的二分方法,它是一种贪婪算法。
它的主要思想是为网络划分定义了一个函数增益Q。
Q表示的是社区内部的边数与社区之间的边数之差。
根据这个方法找出使增益函数Q的值成为最大值的划分社区的方法。
具体策略是,将社区结构中的结点移动到其他的社区结构中或者交换不同社区结构中的结点。从初始解开始搜索,直到从当前的解出发找不到更优的候选解,然后停止。
首先将整个网络的节点随机的或根据网络的现有信息分为两个部分,在两个社团之间考虑所有可能的节点对,试探交换每对节点并计算交换前后的ΔQ,ΔQ=Q交换后-Q交换前,记录ΔQ最大的交换节点对,并将这两个节点互换,记录此时的Q值。
规定每个节点只能交换一次,重复这个过程直至网络中的所有节点都被交换一次为止。需要注意的是不能在Q值发生下降时就停止,因为Q值不是单调增加的,既使某一步交换会使Q值有所下降,但其后的一步交换可能会出现一个更大的Q值。在所有的节点都交换过之后,对应Q值最大的社团结构即被认为是该网络的理想社团结构。
K-L算法的缺陷是必须先指定了两个子图的大小,不然不会得到正确的结果,实际应用意义不大。
Python代码如下:
import networkx as nx import matplotlib.pyplot as plt from networkx.algorithms.community import kernighan_lin_bisection def draw_spring(G, com): """ G:图 com:划分好的社区 node_size表示节点大小 node_color表示节点颜色 node_shape表示节点形状 with_labels=True表示节点是否带标签 """ pos = nx.spring_layout(G) # 节点的布局为spring型 NodeId = list(G.nodes()) node_size = [G.degree(i) ** 1.2 * 90 for i in NodeId] # 节点大小 plt.figure(figsize=(8, 6)) # 图片大小 nx.draw(G, pos, with_labels=True, node_size=node_size, node_color='w', node_shape='.') color_list = ['pink', 'orange', 'r', 'g', 'b', 'y', 'm', 'gray', 'black', 'c', 'brown'] # node_shape = ['s','o','H','D'] for i in range(len(com)): nx.draw_networkx_nodes(G, pos, nodelist=com[i], node_color=color_list[i]) plt.show() if __name__ == "__main__": G = nx.karate_club_graph() # 空手道俱乐部 # KL算法 com = list(kernighan_lin_bisection(G)) print('社区数量', len(com)) print(com) draw_spring(G, com)
这里直接使用了networkx库中的kl算法,数据集Zachary karate club网络是通过对一个美国大学空手道俱乐部进行观测而构建出的一个社会网络.网络包含 34 个节点和 78 条边,其中个体表示俱乐部中的成员,而边表示成员之间存在的友谊关系.空手道俱乐部网络已经成为复杂网络社区结构探测中的一个经典问题。
经过一次kl算法划分为如图两个部分。
社区划分相关的代码与数据集放在github,可以自行下载。
具体的kl算法如下,是networkx库中的算法,可以参考下:
"""Functions for computing the Kernighan–Lin bipartition algorithm.""" import networkx as nx from itertools import count from networkx.utils import not_implemented_for, py_random_state, BinaryHeap from networkx.algorithms.community.community_utils import is_partition __all__ = ["kernighan_lin_bisection"] def _kernighan_lin_sweep(edges, side): """ This is a modified form of Kernighan-Lin, which moves single nodes at a time, alternating between sides to keep the bisection balanced. We keep two min-heaps of swap costs to make optimal-next-move selection fast. """ costs0, costs1 = costs = BinaryHeap(), BinaryHeap() for u, side_u, edges_u in zip(count(), side, edges): cost_u = sum(w if side[v] else -w for v, w in edges_u) costs[side_u].insert(u, cost_u if side_u else -cost_u) def _update_costs(costs_x, x): for y, w in edges[x]: costs_y = costs[side[y]] cost_y = costs_y.get(y) if cost_y is not None: cost_y += 2 * (-w if costs_x is costs_y else w) costs_y.insert(y, cost_y, True) i = totcost = 0 while costs0 and costs1: u, cost_u = costs0.pop() _update_costs(costs0, u) v, cost_v = costs1.pop() _update_costs(costs1, v) totcost += cost_u + cost_v yield totcost, i, (u, v) @py_random_state(4) @not_implemented_for("directed") def kernighan_lin_bisection(G, partition=None, max_iter=10, weight="weight", seed=None): """Partition a graph into two blocks using the Kernighan–Lin algorithm. This algorithm partitions a network into two sets by iteratively swapping pairs of nodes to reduce the edge cut between the two sets. The pairs are chosen according to a modified form of Kernighan-Lin, which moves node individually, alternating between sides to keep the bisection balanced. Parameters ---------- G : graph partition : tuple Pair of iterables containing an initial partition. If not specified, a random balanced partition is used. max_iter : int Maximum number of times to attempt swaps to find an improvemement before giving up. weight : key Edge data key to use as weight. If None, the weights are all set to one. seed : integer, random_state, or None (default) Indicator of random number generation state. See :ref:`Randomness<randomness>`. Only used if partition is None Returns ------- partition : tuple A pair of sets of nodes representing the bipartition. Raises ------- NetworkXError If partition is not a valid partition of the nodes of the graph. References ---------- .. [1] Kernighan, B. W.; Lin, Shen (1970). "An efficient heuristic procedure for partitioning graphs." *Bell Systems Technical Journal* 49: 291--307. Oxford University Press 2011. """ n = len(G) labels = list(G) seed.shuffle(labels) index = {v: i for i, v in enumerate(labels)} if partition is None: side = [0] * (n // 2) + [1] * ((n + 1) // 2) else: try: A, B = partition except (TypeError, ValueError) as e: raise nx.NetworkXError("partition must be two sets") from e if not is_partition(G, (A, B)): raise nx.NetworkXError("partition invalid") side = [0] * n for a in A: side[a] = 1 if G.is_multigraph(): edges = [ [ (index[u], sum(e.get(weight, 1) for e in d.values())) for u, d in G[v].items() ] for v in labels ] else: edges = [ [(index[u], e.get(weight, 1)) for u, e in G[v].items()] for v in labels ] for i in range(max_iter): costs = list(_kernighan_lin_sweep(edges, side)) min_cost, min_i, _ = min(costs) if min_cost >= 0: break for _, _, (u, v) in costs[: min_i + 1]: side[u] = 1 side[v] = 0 A = {u for u, s in zip(labels, side) if s == 0} B = {u for u, s in zip(labels, side) if s == 1} return A, B
这篇关于社区发现算法——KL算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-04TiDB 资源管控的对撞测试以及最佳实践架构
- 2024-07-03万字长文聊聊Web3的组成架构
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现