Eureka AIR delivers breakthrough ideas for toughest innovation challenges, trusted by R&D personnel around the world.

MLkP/CR algorithm-based undirected graph dividing method

An undirected graph and algorithm technology, applied in the direction of digital transmission system, electrical components, transmission system, etc., can solve the problem of not being able to guarantee the self-connectivity of the graph, and achieve the effect of observing the network topology map, uniform distribution, and reducing the total number

Active Publication Date: 2010-06-16
HARBIN INST OF TECH
View PDF0 Cites 12 Cited by
  • Summary
  • Abstract
  • Description
  • Claims
  • Application Information

AI Technical Summary

Problems solved by technology

[0009] In order to solve the problem that the existing undirected graph segmentation method cannot guarantee the self-connectivity of the graph, the present invention proposes an undirected graph segmentation method based on MLkP / CR algorithm

Method used

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
View more

Image

Smart Image Click on the blue labels to locate them in the text.
Viewing Examples
Smart Image
  • MLkP/CR algorithm-based undirected graph dividing method
  • MLkP/CR algorithm-based undirected graph dividing method
  • MLkP/CR algorithm-based undirected graph dividing method

Examples

Experimental program
Comparison scheme
Effect test

Embodiment Construction

[0017] The undirected graph segmentation method based on the MLkP / CR algorithm described in this embodiment is divided into the following three stages:

[0018] Coarsening Phase: undirected graph G to be split 0 (V 0 ,E 0 ) to reduce the undirected graph G 0 (V 0 ,E 0 ) in a number of points into one point, reduced to an undirected graph G n (V n ,E n ), reduce the scale of the topology map, where V 0 is an undirected graph G 0 The set of vertices in E 0 is an undirected graph G 0 The set of middle edges, V n is an undirected graph G n The set of vertices in E n is an undirected graph G n set of middle edges;

[0019] Initial Partitioning Phase: the undirected graph G obtained in the specification phase n (V n ,E n ) to perform k divisions to obtain k subgraphs G i (V i ,E i ), each subgraph G obtained by dividing i (V i ,E i ) are self-connected, each subgraph G i (V i ,E i ) The number of points in ) is basically equal, and the number of cut edges ...

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to View More

PUM

No PUM Login to View More

Abstract

The invention discloses an MLkP / CR algorithm-based undirected graph dividing method, which relates to the technical field of the visualization of a network topological diagram and solves the problem that self-communication of graphs cannot be ensured in the conventional undirected graph dividing method. The method is divided into three stages which are a restriction stage, an initialization sub-stage and an optimization and refinement stage, wherein the restriction stage comprises the step of: performing restriction on an undirected graph G0 (V0, E0) to be divided to reduce the scale of a topological diagram to obtain the undirected graph Gn (Vn, En); the initialization sub-stage comprises the step of: performing k-division on the undirected graph Gn (Vn, En) to obtain k sub-graphs, wherein each sub-graph is self-communicated; and the optimization and refinement stage comprises the step of: performing optimization and refinement on the k sub-graphs and recovering the k sub-graphs into the original graph G0 (V0, E0) to obtain the divided undirected graph G0 (V0, E0). The method of the invention has the advantages of ensuring the self-communication of the interior of each sub-graph and the less association of the sub-graphs and making each part in the graph independent, and can be applied in various fields for the division of the topological diagrams, comprising the fields of parallel computation, VISL design, task planning, geographic information systems GIS and the like.

Description

technical field [0001] The invention relates to the technical field of visualization of network topology diagrams, in particular to the division of network topology diagrams. Background technique [0002] The network topology map plays a huge role in network management. Most of the network management takes the network topology map as the core of operation, that is, it displays the logical connection relationship and other information of network devices such as networks and routers in a graphical way. Directly perform management operations such as configuration, performance, fault, billing, and security in the network topology. [0003] The Internet topology is generally composed of tens of thousands of routers, that is, the number of points and edges in the corresponding network topology map is large, and the connection relationship is complex. It is extremely difficult to plan it directly at this scale, and the time-space complexity It will be very high, and the effect wil...

Claims

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to View More

Application Information

Patent Timeline
no application Login to View More
IPC IPC(8): H04L12/24
Inventor 何慧张伟哲张宏莉杨志王星杨贤青
Owner HARBIN INST OF TECH
Who we serve
  • R&D Engineer
  • R&D Manager
  • IP Professional
Why Eureka
  • Industry Leading Data Capabilities
  • Powerful AI technology
  • Patent DNA Extraction
Social media
Eureka Blog
Learn More
PatSnap group products