influence_propagation.py

"""
影响力传播模型模块
Influence Propagation Model Module
"""

from collections import deque
from graph_storage import SocialNetwork


def k_step_influence(network, start, k):
    """
    计算k步内影响力传播范围
    Calculate influence spread within k steps
    
    Args:
        network (SocialNetwork): 社交网络对象 Social network object
        start (int): 起始用户ID Start user ID
        k (int): 传播步数 Number of steps
        
    Returns:
        int: k步内能影响的用户数 Number of users influenced within k steps
        list: 受影响的用户列表 List of influenced users
    """
    # 使用广度优先搜索实现 k 步影响力传播
    # Implement k-step influence propagation using breadth-first search
    visited = set()  # 记录访问过的节点 Track visited nodes
    queue = deque([(start, 0)])  # 队列保存 (节点, 步数) Queue stores (node, step)
    visited.add(start)
    
    influenced_users = [start]  # 受影响的用户列表 List of influenced users
    
    while queue:
        current_node, current_step = queue.popleft()
        
        # 如果当前步数达到k，则停止传播 If current step reaches k, stop propagation
        if current_step >= k:
            continue
            
        # 获取当前节点的邻居 Get neighbors of current node
        neighbors = network.get_following(current_node)
        
        for neighbor in neighbors:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, current_step + 1))
                influenced_users.append(neighbor)
    
    return len(influenced_users), influenced_users


def bfs_shortest_path(network, start, end):
    """
    使用BFS计算两点间的最短路径
    Calculate shortest path between two points using BFS
    
    Args:
        network (SocialNetwork): 社交网络对象 Social network object
        start (int): 起始节点 Start node
        end (int): 结束节点 End node
        
    Returns:
        list: 最短路径节点列表 Shortest path node list
    """
    if start == end:
        return [start]
        
    visited = set()
    queue = deque([(start, [start])])
    visited.add(start)
    
    while queue:
        current_node, path = queue.popleft()
        
        for neighbor in network.get_following(current_node):
            if neighbor == end:
                return path + [neighbor]
                
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, path + [neighbor]))
    
    return []  # 无路径 No path


def select_seed_users_greedy(network, k_steps, target_coverage, max_seeds=None):
    """
    使用贪心算法选择种子用户以最大化影响力覆盖
    Use greedy algorithm to select seed users to maximize influence coverage
    
    Args:
        network (SocialNetwork): 社交网络对象 Social network object
        k_steps (int): 传播步数 Number of propagation steps
        target_coverage (int): 目标覆盖用户数 Target number of users to cover
        max_seeds (int): 最大种子用户数 Maximum number of seed users (optional)
        
    Returns:
        list: 选择的种子用户列表 Selected seed users list
    """
    if max_seeds is None:
        max_seeds = network.n  # 默认最多选择所有节点 Default to selecting all nodes if needed
        
    selected_seeds = []
    covered_nodes = set()
    
    # 贪心算法：每一步选择能覆盖最多未覆盖节点的用户
    # Greedy algorithm: At each step, select the user that covers the most uncovered nodes
    for _ in range(max_seeds):
        if len(covered_nodes) >= target_coverage:
            break
            
        best_user = None
        best_coverage = -1
        
        # 遍历所有可能的种子用户 Iterate through all possible seed users
        for user in range(network.n):
            # 如果用户已经在种子列表中，跳过 Skip if user is already in seed list
            if user in selected_seeds:
                continue
                
            # 计算该用户k步内的影响力 Calculate influence of this user within k steps
            _, influenced_users = k_step_influence(network, user, k_steps)
            
            # 计算该用户能新增覆盖的节点数 Calculate additional nodes this user can cover
            newly_covered = set(influenced_users) - covered_nodes
            new_coverage = len(newly_covered)
            
            # 更新最佳用户 Update best user if this one covers more
            if new_coverage > best_coverage:
                best_coverage = new_coverage
                best_user = user
        
        # 如果没有找到能增加覆盖的用户，结束 If no user increases coverage, end
        if best_user is None or best_coverage == 0:
            break
            
        # 将最佳用户加入种子列表 Add best user to seed list
        selected_seeds.append(best_user)
        
        # 更新已覆盖节点 Update covered nodes
        _, influenced_users = k_step_influence(network, best_user, k_steps)
        covered_nodes.update(influenced_users)
    
    return selected_seeds


# 扩展SocialNetwork类以包含影响力传播方法
class InfluencePropagationNetwork(SocialNetwork):
    """
    具有影响力传播功能的社交网络类
    Social Network class with influence propagation functionality
    """
    
    def k_step_influence(self, start, k):
        """
        计算k步内影响力传播范围
        Calculate influence spread within k steps
        
        Args:
            start (int): 起始用户ID Start user ID
            k (int): 传播步数 Number of steps
            
        Returns:
            int: k步内能影响的用户数 Number of users influenced within k steps
            list: 受影响的用户列表 List of influenced users
        """
        return k_step_influence(self, start, k)
    
    def bfs_shortest_path(self, start, end):
        """
        使用BFS计算两点间的最短路径
        Calculate shortest path between two points using BFS
        
        Args:
            start (int): 起始节点 Start node
            end (int): 结束节点 End node
            
        Returns:
            list: 最短路径节点列表 Shortest path node list
        """
        return bfs_shortest_path(self, start, end)
    
    def select_seed_users_greedy(self, k_steps, target_coverage, max_seeds=None):
        """
        使用贪心算法选择种子用户以最大化影响力覆盖
        Use greedy algorithm to select seed users to maximize influence coverage
        
        Args:
            k_steps (int): 传播步数 Number of propagation steps
            target_coverage (int): 目标覆盖用户数 Target number of users to cover
            max_seeds (int): 最大种子用户数 Maximum number of seed users (optional)
            
        Returns:
            list: 选择的种子用户列表 Selected seed users list
        """
        return select_seed_users_greedy(self, k_steps, target_coverage, max_seeds)


# 测试示例
if __name__ == "__main__":
    print("影响力传播模型 - 示例运行")
    print("Influence Propagation Model - Example Run")
    
    # 创建一个影响力传播网络 Create an influence propagation network
    network = InfluencePropagationNetwork(10, directed=True, storage_type="adj_list")
    
    # 添加一些边 Add some edges
    edges = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4), (4, 5), (5, 6), (6, 7), (7, 8), (8, 9)]
    for u, v in edges:
        network.add_edge(u, v)
    
    print(f"添加了 {len(edges)} 条边")
    print(f"Added {len(edges)} edges")
    
    # 测试影响力传播 Test influence propagation
    affected_count, affected_users = network.k_step_influence(0, 3)
    print(f"从用户0开始3步内影响了 {affected_count} 个用户: {affected_users}")
    print(f"Affected {affected_count} users within 3 steps from user 0: {affected_users}")
    
    # 测试种子用户选择 Test seed user selection
    seed_users = network.select_seed_users_greedy(k_steps=2, target_coverage=5, max_seeds=3)
    print(f"选择了 {len(seed_users)} 个种子用户以覆盖至少5个用户: {seed_users}")
    print(f"Selected {len(seed_users)} seed users to cover at least 5 users: {seed_users}")