随机行走获得不良结果 [英] Get bad result for random walk

问题描述

我想实现随机游走并计算稳态.

I want to implement random walk and compute the steady state.

假设我的图形如下图所示:

Suppose my graph is given as in the following image:

上面的图在文件中定义如下:

The graph above is defined in a file as follows:

1   2   0.9
1   3   0.1
2   1   0.8
2   2   0.1
2   4   0.1
etc

要阅读并构建此图，我使用以下方法:

To read and build this graph, I use the following method:

def _build_og(self, original_ppi):
""" Build the original graph, without any nodes removed. """

try:
    graph_fp = open(original_ppi, 'r')
except IOError:
    sys.exit("Could not open file: {}".format(original_ppi))

G = nx.DiGraph()
edge_list = []

# parse network input
for line in graph_fp.readlines():
    split_line = line.rstrip().split('\t')
    # assume input graph is a simple edgelist with weights
    edge_list.append((split_line[0], split_line[1],  float(split_line[2])))

G.add_weighted_edges_from(edge_list)
graph_fp.close()
print edge_list

return G

在上面的函数中，我需要将图形定义为DiGraph还是simpy Graph?

In the function above do I need to define the graph as DiGraph or simpy Graph?

我们构建过渡矩阵如下:

We build the transition matrix as following:

def _build_matrices(self, original_ppi, low_list, remove_nodes):
        """ Build column-normalized adjacency matrix for each graph.

        NOTE: these are column-normalized adjacency matrices (not nx
              graphs), used to compute each p-vector
        """
        original_graph = self._build_og(original_ppi)
        self.OG = original_graph
        og_not_normalized = nx.to_numpy_matrix(original_graph)
        self.og_matrix = self._normalize_cols(og_not_normalized)

然后我使用:

def _normalize_cols(self, matrix):
        """ Normalize the columns of the adjacency matrix """
        return normalize(matrix, norm='l1', axis=0)

现在要模拟我们定义的随机游走:

now to simulate the random walk we define :

def run_exp(self, source):

        CONV_THRESHOLD = 0.000001
        # set up the starting probability vector
        p_0 = self._set_up_p0(source)
        diff_norm = 1
        # this needs to be a deep copy, since we're reusing p_0 later
        p_t = np.copy(p_0)

        while (diff_norm > CONV_THRESHOLD):
            # first, calculate p^(t + 1) from p^(t)
            p_t_1 = self._calculate_next_p(p_t, p_0)

            # calculate L1 norm of difference between p^(t + 1) and p^(t),
            # for checking the convergence condition
            diff_norm = np.linalg.norm(np.subtract(p_t_1, p_t), 1)

            # then, set p^(t) = p^(t + 1), and loop again if necessary
            # no deep copy necessary here, we're just renaming p
            p_t = p_t_1

我们使用以下方法定义初始状态(p_0):

We define the initial state (p_0) by using the following method:

def _set_up_p0(self, source):
    """ Set up and return the 0th probability vector. """
    p_0 = [0] * self.OG.number_of_nodes()
    # convert self.OG.number_of_nodes() to list
    l =  list(self.OG.nodes())
    #nx.draw(self.OG, with_labels=True)
    #plt.show()
    for source_id in source:
        try:
            # matrix columns are in the same order as nodes in original nx
            # graph, so we can get the index of the source node from the OG
            source_index = l.index(source_id)
            p_0[source_index] = 1 / float(len(source))
        except ValueError:
            sys.exit("Source node {} is not in original graph. Source: {}. Exiting.".format(source_id, source))

    return np.array(p_0)  

要生成下一个状态，我们使用以下函数

To generate the next state, we use the following function

和功率迭代策略:

def _calculate_next_p(self, p_t, p_0):
        """ Calculate the next probability vector. """
        print 'p_0\t{}'.format(p_0)
        print 'p_t\t{}'.format(p_t)
        epsilon = np.squeeze(np.asarray(np.dot(self.og_matrix, p_t)))
        print 'epsilon\t{}'.format(epsilon)
        print 10*"*"
        return np.array(epsilon)

假设随机游走可以从任何节点(1、2、3或4)开始.

Suppose the random walk can start from any node (1, 2, 3 or 4).

运行代码时，我得到以下结果:

When runing the code i get the following result:

2       0.32
3       0.31
1       0.25
4       0.11

结果必须是:

(0.28, 0.30, 0.04, 0.38).

那么有人可以帮助我发现我的错误在哪里吗?

So can someone help me to detect where my mistake is?

我不知道问题是否出在我的转换矩阵中.

I don't know if the problem is in my transition matrix.

推荐答案

这里是矩阵(应该是过渡矩阵从左边乘以状态向量，这是一个左随机矩阵 >，其中列加起来为1，(i, j)项是从j到i的概率.

Here is what the matrix should be (given than your transition matrix multiplies the state vector from the left, it is a left stochastic matrix, where the columns add up to 1, and the (i, j) entry is the probability of going from j to i).

import numpy as np
transition = np.array([[0, 0.8, 0, 0.1], [0.9, 0.1, 0.5, 0], [0.1, 0, 0.3, 0], [0, 0.1, 0.2, 0.9]])
state = np.array([1, 0, 0, 0])    # could be any other initial position
diff = tol = 0.001
while diff >= tol:
    next_state = transition.dot(state)
    diff = np.linalg.norm(next_state - state, ord=np.inf)
    state = next_state
print(np.around(state, 3))

这将打印[0.279 0.302 0.04 0.378].

我无法确定您是错误地加载数据还是其他原因. 列归一化"步骤是一个警告信号:如果给定的转换概率不等于1，则应报告错误数据，而不是对列进行归一化.而且我不知道为什么当数据已经以矩阵形式呈现时，为什么根本不使用NetworkX:给定的表可以读为

I can't tell if you are loading the data incorrectly, or something else. The step with "column normalization" is a warning sign: if the given transition probabilities don't add up to 1, you should report bad data, not normalize the columns. And I don't know why you use NetworkX at all when the data is already presented as a matrix: the table you are given can be read as

column   row   entry 

这个矩阵是计算所需要的.

and this matrix is what is needed for calculations.

这篇关于随机行走获得不良结果的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！