Determination of Network Topology by Matrix Partial Multiplication

Slowness is a crucial factor to prevent matrix method from its practical use in network topology. The matrix method which gets full connectivity matrix by multiplying the adjacency matrix repeatedly and determines connective sets by comparing or scanning rows of the full connectivity matrix is very time-consuming. Nodes in a connective set have same rows in the full connectivity matrix, the connective set can be determined by the first row of these same rows. Calculation of other rows whose connective set is fixed by the preceding rows is unnecessary. Once a node is certain in an exist connective set, the calculation of the row related to the node can be stopped. Based on the above consideration, a network topology method by matrix partial multiplication is presented. Row comparing or scanning is unnecessary in the presented method, and sparse matrix techniques, connectivity matrix elements immediately updating, optical node numbering are also used in the presented method. All these measures greatly decrease calculation and speed up the network topology. A practical network being analyzed by the proposed method is presented, and the results prove the effectiveness of the proposed method.