CN113660116B - Weak-communication directed acyclic scale-free network generation method - Google Patents
Weak-communication directed acyclic scale-free network generation method Download PDFInfo
- Publication number
- CN113660116B CN113660116B CN202110862087.3A CN202110862087A CN113660116B CN 113660116 B CN113660116 B CN 113660116B CN 202110862087 A CN202110862087 A CN 202110862087A CN 113660116 B CN113660116 B CN 113660116B
- Authority
- CN
- China
- Prior art keywords
- node
- nodes
- network
- sequence
- undirected
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Active
Links
Images
Classifications
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L41/00—Arrangements for maintenance, administration or management of data switching networks, e.g. of packet switching networks
- H04L41/12—Discovery or management of network topologies
Landscapes
- Engineering & Computer Science (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- Data Exchanges In Wide-Area Networks (AREA)
Abstract
本发明属于无线网络技术领域，公开了一种弱连通有向无环无标度网络生成方法，包括：创建m个节点的小型随机网络，随机决定m个节点之间是否存在无向连接；依次添加新的节点至网络中，对每次添加的新节点确定与k个旧节点之间的连接关系；将网络中的节点按照节点的度数从小到大排序，调整序列；将生成的序列作为最终的拓扑排序序列对无向图进行定向，所有无向边方向都已确定，则结束。本发明提供的弱连通的有向无环无标度网络生成方法，能快速生成符合幂律分布的有向无环的无标度网络，同时保证该网络弱连通(有向图的基图是连通的，但任意两点之间不一定有通路)、每个节点的出度和入度均匀。
The invention belongs to the technical field of wireless networks, and discloses a method for generating a weakly connected directed acyclic and scale-free network, comprising: creating a small random network with m nodes, and randomly determining whether there is an undirected connection between the m nodes; Add new nodes to the network, and determine the connection relationship with k old nodes for each new node added; sort the nodes in the network according to the degree of the nodes from small to large, and adjust the sequence; take the generated sequence as the final The topological sort sequence orients the undirected graph and ends when all undirected edge directions are determined. The method for generating a weakly connected directed acyclic scale-free network provided by the present invention can quickly generate a directed acyclic scale-free network that conforms to the power-law distribution, while ensuring that the network is weakly connected (the base graph of the directed graph is connected, but there is not necessarily a path between any two points), and the out-degree and in-degree of each node are uniform.
Description
Technical Field
The invention belongs to the technical field of wireless networks, and particularly relates to a weak-connectivity directed acyclic scale-free network generation method.
Background
In 1999, it was found in empirical observations of the world wide web and the internet in autonomous systems that the distribution of the degree of nodes in these networks closely approximated a power law distribution, and the nature of the scale-free network was first discovered. Previously, research on networks, particularly complex networks, has focused primarily on random networks. In a random network, the probability of connection between each pair of nodes is a constant p (1< p < 1). The data that each node connects to other nodes is called the degree of this node. In a random network, the distribution of node degrees is highly uniform, most of the node degrees are concentrated near a certain special value, the probability of deviation from the special value is very little, and the degree of the whole network presents a bell-shaped Poisson distribution. In contrast, there is a power-law distribution of the degree of the scale-free network nodes.
Unlike the uniform distribution of connectivity of random network nodes, the world wide web is strung together by a small number of highly-connected nodes. Most web pages have no more than 4 hyperlinks, but very few pages have more than 1000 multilinks. It is finally found that the power of the nodes in such a network conforms to a power law distribution, also known as pareto distribution. Scaleless networks have wide application in various fields, and the present invention focuses on the evolution of a directed acyclic scaleless network.
In a general sense, there are two points to the generation of a scaleless network. Firstly, the network size needs to be continuously enlarged by continuously adding new nodes to the network, and secondly, connectivity is preferred. Taking the world wide web connection as an example, although the web sites are hundreds of millions, people often connect to only a small portion of their familiar web portals that contain more connections. As another example, when joining a social network for the first time, new people are more likely to stay in contact with important people or people celebrities in the community; in the internet, routers with a high number of connections tend to have a larger bandwidth and are further selected by new users.
Most of the current scale-free network generation methods are directed to undirected graphs, that is, once a connection exists in a network, the connection is just two-way reachable, but the method is only a simplification of a real directed network. To express a directed network, an intuitive approach is to directly randomly orient the connections of the generated undirected unscaled network, randomly assign a direction to be reachable, and fail to be reachable in the reverse direction. This method cannot avoid loops in the network, and the existence of loops will cause inconvenience to the network's traversal, spanning tree construction, routing, etc. After finding the loop, there are two methods to deal with, the first is to directly reverse the weight and then to re-orient the whole body randomly, the second is to try to change the direction of some key edges in the network, and both methods are very complex.
At present, some only works aiming at the generation of the directed scaleless network need to recalculate the out-degree and the in-degree of the existing nodes once and then select old nodes to be connected in each iteration step of the dynamic extension of the network, namely when each newly-added node is connected with the old node, the complexity of the method is too high, the execution speed is slow, and the problem of the occurrence of loops is not considered.
Through the above analysis, the problems and defects of the prior art are as follows:
(1) the existing method directly orients the generated connections of the undirected and scaleless network at random, and can not avoid loops in the network, and the existence of the loops brings inconvenience to the work of traversing the network, constructing a spanning tree, routing and the like. When traversing the network, if a loop exists and the path is not calibrated, endless loop occurs, and the network cannot exit after repeated rotation. Similarly, the process of constructing the spanning tree needs to determine its parent node for each node, and if the loop is not excluded, the parent nodes of some nodes are quite likely to be determined as the points on the loop, and finally contradict the definition of the tree (the loop-free hierarchical structure).
(2) At present, only the work for generating the directed scale-free network needs to recalculate the degree of departure and the degree of entry of the existing nodes once and then make a selection of old nodes to be connected when establishing connection between each new node and the old node, the method has too high complexity and low execution speed, does not consider the problem of loop occurrence, needs to add subsequent steps to eliminate the loop, and has increased complexity.
The difficulty in solving the above problems and defects is: after finding the loop, two methods are used for processing, the first method is that each edge is randomly oriented in the process of constructing the directed network, once the loop is encountered, the weight is directly reversed, and the whole random orientation is performed again; the second is to selectively redirect some critical edges in the network, both of which are very complex.
The significance for solving the problems and the defects is as follows: in order to reduce complexity, the invention does not carry out orientation and loop judgment for each edge in the process of constructing the network, but constructs a non-oriented scale-free network firstly, then randomly generates a topological ordering sequence, and directly orients all the edges at one time according to the sequence. The finally generated directed graph is ensured to be acyclic according to the concept and the property of topological sorting, the solution is clear and concise, the complexity is low, and the effect is good.
Disclosure of Invention
Aiming at the problems in the prior art, the invention provides a weak-connectivity directed acyclic unscaled network generation method.
The invention is realized in such a way that a weak-connection directed acyclic unscaled network generation method comprises the following steps:
step one, a small random network of m nodes is established; wherein m is a given parameter, and m nodes are randomly connected;
step two, adding new nodes into the network one by one, and providing that each newly added node is connected with K nodes in the current network at most and preferentially connected with nodes with large numbers in the current network; repeating the second step until the number of the nodes in the network reaches the specified number | V |;
step three, judging whether the undirected graph is communicated, if so, executing step five; otherwise, executing the step four;
step four, deleting the minimum connected component in the network, and executing the step two;
counting degrees of all nodes in the network, and performing topological sequencing on all nodes according to the sequence of the degrees from small to large;
step six, adjusting the sequencing sequence to ensure that the degrees of the nodes in the sequence are sequentially decreased from the middle to the two ends, and using the sequence as a final topology sequencing sequence of the directed network;
step seven, orienting the generated edges in the connected undirected small-world network one by one; deleting undirected edges (i, j) in the network, investigating the bit order relation between the nodes i and the nodes j in the topological sorting sequence, and if the nodes i are arranged in front of the nodes j, adding the directed edges to point to the nodes j from the i; otherwise, adding a directed edge starting from the node j to the node i;
step eight, judging whether the orientation of all edges is finished, if so, finishing the process; otherwise, the step seven is continuously executed.
In the above steps, the goal of steps one through four is to generate a connected undirected scaleless network, which is the basis for the subsequent steps. And step four and step five, in order to generate a topological sorting sequence with good performance. In theory, any random sequence can be used as a topological ordering sequence of the network, and any sequence can be used for orienting edges, so that the final directed graph can be ensured to be acyclic in concept. However, because the order of establishing directed connections is from front to back, the nodes at the front end of the sequence have many outgoing connections, and similarly, the nodes at the back end of the sequence have many incoming connections. Therefore, the nodes with high degrees are arranged in the middle of the sequence, and the nodes can be ensured to have both the incoming edges and the outgoing edges to the greatest extent. Nodes with low degrees are at two ends of the sequence, and although the degrees of the nodes are not uniform, the degrees of the nodes are low, and the degree of the nodes is low, so that the influence on the network connectivity is limited. Such considerations may maximize the connectivity of the final network.
Further, in step two, the method for establishing the ith (i < k is more than or equal to 1) connection includes:
counting the degrees of all the old nodes to generate a total degree interval, wherein the interval corresponding to each old node is directly related to the degree of the old node; randomly generating a random number r uniformly distributed in a degree interval, and inspecting whether connection exists between a new node and an old node corresponding to the interval according to the interval in which r is distributed; if not, namely A (new node, old node) is 0 in the two-dimensional matrix currently representing the node relationship, then let A (new node, old node) be A (old node, new node) be 1, and continue the next selection; if a connection is already present, a new random number is regenerated and the trial is repeated.
Further, the method for generating the weakly-connected directed acyclic unscaled network further comprises the steps of creating an undirected unscaled network with N nodes; wherein, the creation process of the undirected scaleless network comprises the following steps:
(1) creating a small random network: setting the number of initial nodes in the small network as M, and the number of nodes in the finally generated scale-free network as N, wherein M < < N; firstly, generating M nodes, then randomly generating the relationship among the M nodes, and storing the relationship among the nodes in the network by adopting an adjacency matrix A; a (i, j) ═ 1 represents that there is a directed edge between the node i and the node j, and a (i, j) ═ 0 cannot reach the node j from the node i; the value of A (i, j) is obtained by randomly generating a decimal between 0 and 1 and rounding; in a undirected network, undirected edges are bi-directionally reachable, i.e., a (i, j) ═ a (j, i), i.e., matrix a, is a symmetric matrix.
(2) Continuously expanding the network by newly adding nodes, and selecting an old node connected with each newly added node by using preferred connectivity as a criterion until the number of nodes in the network reaches N; the preferred connection performance can ensure that the newly added node is preferentially connected to the old node with better connectivity, and the preferred connection performance is realized by generating a probability value matched with the connectivity of the node; assuming that each new node needs to connect k old nodes, k being a given constant; finally, a connected undirected scaleless network is generated, namely the directed graph is connected with the base graph, and the final directed graph is ensured to be weakly connected.
(3) After a network with the number of nodes being N is generated, counting and solving the distribution of all node degrees in the network; wherein, the statistical method comprises the following steps: counting the degree of each node, and then removing the duplication of the result, namely solving the number of the non-repeated degrees in the network; and counting to obtain the number of nodes corresponding to each degree, and dividing the number by the total number of the degrees to obtain the distribution of the degrees. Five nodes are arranged in the network, and the degrees of the nodes are 2,2,4,5 and 5 respectively; the non-repeating degree is 2,4,5, and the number of nodes falling in the interval of 2,4,5 is 2,1,2, respectively, so that the frequency of degree 2,4,5 is 0.4,0.2,0.4, respectively.
Further, in step (2), the method for establishing a connection for the new _ node at the ith time (i < ═ k) includes:
firstly, scanning an adjacency matrix, counting the degree of each node, and then constructing a numerical interval matched with the degree of the node; if the fixed network has three old nodes a, b, and c, each of which is 2,8, and 4, an interval with a total interval length of 2+8+4 equal to 14 degrees needs to be constructed, and each cell has [1,2], [3,10], [11, and 14 ]. In order to preferentially connect the newly added node to the old node with better connectivity, an integer r uniformly distributed in the interval [1,14] is randomly generated, and the r falls into one of the three intervals, and is supposed to fall into the interval range of [11,14] corresponding to the third, namely c node. If the newly added node is not connected with a third node at present, namely the current a (new _ node, c) is equal to 0, the corresponding a (new _ node, c) and a (c, new _ node) are assigned to be 1, and the selected neighbor is added with 1; otherwise, if the selected point has passed the new _ node, continuing to generate the random numbers distributed in [1,14], and continuing to select the neighbor.
Further, the method for generating the weakly-connected directed acyclic unscaled network further includes the step of orienting the undirected edge by generating a topological ordering sequence of the network, including:
topological sorting is a process of linearizing a nonlinear structure, and all nodes in a graph are arranged into a linear sequence, so that if an edge (u, v) belongs to a directed graph G, a node u is always in front of the node v in a final linear sequence; conversely, if node u precedes node v in the sorted sequence, if there is an edge between uv, the direction must be from node u to node v; the nature of topological sorting can ensure that the final directed graph is acyclic, and the edge attached to the point at the front end of the sequence is mainly emitted from the point, and the edge attached to the point at the rear end of the sequence is mainly emitted to the point; arranging nodes in the network from small to large according to the illumination intensity, sequentially adjusting the obtained sequence, and placing the node with the maximum degree at the middle of the sequence to ensure that the edges attached to the nodes with the large degree have emission and incidence, and the entrance and exit degrees are as uniform as possible; and taking the final sequence as a topological ordering sequence, and orienting all the non-oriented edges at one time.
Further, the generating a topology ranking sequence of the network and directing the undirected edges further includes:
(1) counting the degree of each node in the network, and sequencing all the nodes in sequence from small to large according to the illumination intensity; wherein, the degree of a node is the number of edges attached to the node.
(2) The order of the node sequence with the degrees from small to large generated as above is adjusted, the node with the maximum degree is placed in the middle, and the nodes with the degrees from the middle to the two sides are respectively placed at the two sides, namely, the degrees of the nodes from the middle to the two sides are sequentially decreased.
(3) The finally obtained sequence is a topological sorting sequence, and all the undirected edges are oriented by using the topological sorting sequence; assuming that the sequence has N nodes, and in an iterative mode, the edge 1 emitted by the ith node in the sequence is not less than i and not more than N each time the sequence is examined; examine the ith node in turn i Node m in the sequence following the node m m The value range of m is from the (i + 1) th to the (N) th; (iv) a quinone i And a node m There is an undirected edge between them, so that when the edge is oriented, the direction of the edge is determined by the node i Is emitted to the node m (ii) a After the relations between all the (i + 1) th to Nth nodes and the ith node are considered circularly, the size of i is increased by 1, and all the emitted edges of the next node are oriented continuously; and sequentially circulating until i is equal to N +1, and finishing the whole process.
Another object of the present invention is to provide a system for generating a weakly-connected directed acyclic unscaled network using the method for generating a weakly-connected directed acyclic unscaled network, wherein the system for generating a weakly-connected directed acyclic unscaled network comprises:
the random network creating module is used for creating a small random network of m nodes and randomly determining whether undirected connection exists between the m nodes;
the node adding module is used for sequentially adding new nodes into the network and determining the connection relation between the new nodes and k old nodes for each added new node;
the node sequencing module is used for sequencing the nodes in the network from small to large according to the degrees of the nodes and adjusting the sequence to ensure that the degrees of the nodes from the middle part to the two ends are reduced in sequence;
the undirected graph orientation module is used for orienting the undirected graph by taking the generated sequence as a final topological sorting sequence, positioning each node i in the sequence and scanning each node j behind the node i in the sequence in turn; if there is an undirected edge between the node i and the node j in the base graph, the direction of the edge is shot to the node j by the node i; and ending when all the non-side directions are determined.
It is a further object of the invention to provide a computer device comprising a memory and a processor, the memory storing a computer program which, when executed by the processor, causes the processor to perform the steps of:
creating a small random network of m nodes, and randomly determining whether undirected connection exists between the m nodes; sequentially adding new nodes into the network, and determining the connection relation between the new nodes added each time and k old nodes; sequencing the nodes in the network from small to large according to the degrees of the nodes, and adjusting the sequence to ensure that the degrees of the nodes from the middle part to the two ends are reduced in sequence; taking the generated sequence as a final topological sorting sequence to orient the undirected graph, positioning each node i in the sequence, and scanning each node j behind the node i in the sequence in turn; if there is an undirected edge in the base graph between i and j, the direction of the edge is from i to j, and the complexity of the whole operation is O (n) 2 ) (ii) a All the non-edgewise directions have been determined, the whole process ends.
It is another object of the present invention to provide a computer-readable storage medium storing a computer program which, when executed by a processor, causes the processor to perform the steps of:
creating a small random network of m nodes, and randomly determining whether undirected connection exists between the m nodes; sequentially adding new nodes into the network, and determining the connection relation between the new nodes added each time and k old nodes; sequencing the nodes in the network from small to large according to the degrees of the nodes, and adjusting the sequence to ensure that the degrees of the nodes from the middle part to the two ends are reduced in sequence; taking the generated sequence as a final topological sorting sequence to orient the undirected graph, positioning each node i in the sequence, and scanning each node j behind the node i in the sequence in turn; if there is a one in the base graph between i and jThe bar has no side, then the side is directed from i to j, and the complexity of the whole operation is O (n) 2 ) (ii) a All the non-edgewise directions have been determined, the whole process ends.
Another object of the present invention is to provide an information data processing terminal for implementing the said weakly connected directed acyclic unscaled network generation system.
By combining all the technical schemes, the invention has the advantages and positive effects that: the method for generating the weakly-connected directed acyclic unscaled network can quickly generate the directed acyclic unscaled network conforming to power law distribution, simultaneously ensure that the network is weakly connected (the base graph of the directed graph is connected, but a passage is not necessarily arranged between any two points), and the out-degree and the in-degree of each node are uniform.
The invention belongs to the field of complex networks, and particularly relates to directed acyclic random scale-free network generation. In a scale-free network, the degree of most nodes (the number of nodes connected to other nodes) is low, and only a small number of nodes have a high degree. The scale-free network can simulate many networks in the real world, such as the crowd relationships of social networks, the debit and credit relationships between institutions in financial networks, airline paths in airline networks, and so on. And thus related research has received a great deal of attention. Most of the current random scale-free network generation methods only involve undirected graphs, i.e., communication between nodes is bidirectional if any. Nodes in a real-world scale-free network tend to be in unequal positions, so that connections tend to be asymmetric directional connections. The work in the aspect of generating the directed scaleless network is less, and meanwhile, the existing method cannot ensure that the generated directed network does not contain a ring. The method can quickly generate the directed acyclic scale-free network which accords with the power law distribution, and simultaneously ensures that the network is weakly connected and the access degrees of the nodes are uniform.
Unlike random networks, the scale of the scale-free network nodes conforms to a power law distribution, and there are many application examples in reality. Most of the existing scale-free network generation methods are directed to undirected graphs. In actual wireless transmission application, the communication scene based on the directed graph is wider, and the characteristic of no loop can provide convenience for traversing and routing algorithms of the network. The present invention concerns the generation of a scale-free network of directed acyclic. In terms of a generation method, the method abandons methods with higher computational complexity such as a broken circle method and the like for removing the loop after randomly calibrating the direction, and also avoids the problem that each edge is oriented in the generation process of the network and the in-out degree of the existing node needs to be continuously calculated. The invention generates the topological sequencing sequence of all nodes on the basis of the undirected scale-free network to directly orient all undirected edges. In the sequence, the point with the largest node degree (without distinguishing the degree and the degree) in the undirected graph is arranged in the middle of the sequence, and the node degrees at the two ends of the sequence are smaller as the undirected graph is more deviated. The invention can quickly generate the scale-free network with directed acyclic, and ensure the directed graph is weakly connected, namely the base graph of the directed graph is a connected graph. The invention can support the simulation of various wireless network communication scenes by the communication bottom infrastructure.
Drawings
In order to more clearly illustrate the technical solutions of the embodiments of the present invention, the drawings needed to be used in the embodiments of the present invention will be briefly described below, and it is obvious that the drawings described below are only some embodiments of the present invention, and it is obvious for those skilled in the art that other drawings can be obtained according to the drawings without creative efforts.
Fig. 1 is a flowchart of a method for generating a weakly connected directed acyclic unscaled network according to an embodiment of the present invention.
Fig. 2 is a schematic diagram of a method for generating a weakly connected directed acyclic scaleless network according to an embodiment of the present invention.
FIG. 3 is a block diagram of a weakly connected directed acyclic unscaled network generation system according to an embodiment of the present invention;
in the figure: 1. a random network creation module; 2. a node adding module; 3. a node sorting module; 4. and an undirected graph orientation module.
FIG. 4 is an undirected graph orientation illustration provided by an embodiment of the invention;
in the figure: (a) undirected graph; (b) the nodes are sorted from small to large according to the illumination intensity, wherein the degrees of the C node and the D node are the same; (c) adjusting the order of the nodes to make the node with the largest degree arranged in the middle and the degrees of the nodes at the two ends reduced in sequence; (d) and (d) taking the sequence in the step (c) as a topological sorting sequence, and orienting the undirected graph to obtain the directed graph.
FIGS. 5(a) and 5(b) are illustrations of the distribution of node degrees in an undirected, scaleless network provided by embodiments of the present invention;
in the figure: the initial network comprises 5 nodes, and each newly added node is connected with 3 old nodes; fig. 5(a) shows 1000 nodes, and fig. 5(b) shows 5000 nodes.
Fig. 6(a), fig. 6(b) and fig. 6(c) are schematic diagrams of directed scale-free networks with 8 nodes, 30 nodes and 3000 nodes, respectively, generated by the present invention according to an embodiment of the present invention;
in the figure: fig. 6(a) shows 8, fig. 6(b) shows 30, and fig. 6(c) shows 3000.
Detailed Description
In order to make the objects, technical solutions and advantages of the present invention more apparent, the present invention is further described in detail with reference to the following embodiments. It should be understood that the specific embodiments described herein are merely illustrative of the invention and do not limit the invention.
In view of the problems in the prior art, the present invention provides a method for generating a weakly connected, directed, acyclic, and scaleless network, and the present invention is described in detail below with reference to the accompanying drawings.
As shown in fig. 1, a method for generating a weakly connected directed acyclic unscaled network according to an embodiment of the present invention includes the following steps:
s101, creating a small random network of m nodes; wherein m is a given parameter, randomly connecting m nodes;
s102, adding new nodes into the network one by one, and providing that each newly added node is connected with K nodes in the current network at most and preferentially connected with nodes with large numbers in the current network; repeating S102 until the number of nodes in the network reaches a specified number | V |;
s103, judging whether the undirected graph is communicated, if so, performing S105, otherwise, performing S104;
s104, deleting the minimum connected component in the network, and executing S102;
s105, counting the degrees of all nodes in the network, and carrying out topological sorting on all the nodes according to the sequence of the degrees from small to large;
s106, adjusting the sequencing sequence to enable the degree of the nodes in the sequence to be sequentially decreased from the middle to the two ends, and using the sequence as a final topology sequencing sequence of the directed network;
s107, orienting the generated edges in the connected undirected small-world network one by one; deleting undirected edges (i, j) in the network, observing the bit order relationship between the nodes i and the nodes j in the topological sorting sequence, and adding directed edges to point to the nodes j from the nodes i if the nodes i are arranged in front of the nodes j; otherwise, adding a directed edge starting from the node j to the node i;
s108, judging whether the orientation of all the edges is finished or not, if so, finishing the process; otherwise, execution continues with S107.
A schematic diagram of a method for generating a weakly-connected directed acyclic unscaled network according to an embodiment of the present invention is shown in fig. 2.
As shown in fig. 3, the weakly connected directed acyclic unscaled network generation system provided by the embodiment of the present invention includes:
the random network creating module 1 is used for creating a small random network of m nodes and randomly determining whether undirected connection exists between the m nodes;
the node adding module 2 is used for sequentially adding new nodes into the network and determining the connection relation between the new nodes and k old nodes for each added new node;
the node sequencing module 3 is used for sequencing the nodes in the network from small to large according to the degrees of the nodes, and adjusting the sequence to enable the degrees of the nodes from the middle part to the two ends to be reduced in sequence;
an undirected graph orientation module 4, configured to orient an undirected graph by using the generated sequence as a final topological sorting sequence, locate each node i in the sequence, and sequentially scan each node j behind the node i in the sequence; if there is an undirected edge between the node i and the node j in the base graph, the direction of the edge is shot to the node j by the node i; and ending when all the non-side directions are determined.
The technical solution of the present invention is further described below with reference to examples.
Example 1
Aiming at the problems in the prior art, the invention provides a rapid generation method of a directed acyclic scaleless network. In terms of a generation method, the method abandons methods with higher calculation complexity, such as a circle-breaking method and the like, for removing the loop after randomly calibrating the direction, and also avoids the situation that each edge is oriented in the generation process of the network and the in-out degree of the existing node needs to be continuously calculated. The invention generates a topological sequencing sequence of all nodes on the basis of a undirected scale-free network to directly orient all undirected edges. In this sequence, the point with the largest node degree (indistinguishable degree and degree of entry) in the undirected graph is arranged in the middle of the sequence, and the node degrees which are more biased to the two ends of the sequence are smaller. The invention can quickly generate the scale-free network with directed acyclic, and ensure the directed graph is weakly connected, namely the base graph of the directed graph is a connected graph. The invention can be used as a bottom infrastructure to support the simulation of various wireless network communication scenes.
The technical scheme adopted by the invention is as follows:
in the first step, an undirected, scaleless network with a number of nodes N is created. The specific creation process is set forth below:
I. a small random network is created. In the small network, the number of initial nodes is M, the number of nodes in the finally generated scale-free network is N, and M < < N. To complete this step, M nodes need to be generated first, and then the relationships among the M nodes are generated randomly. The invention uses an adjacency matrix a to store the relationships between nodes in the network. A (i, j) ═ 1 represents that there is a directed edge between the node i and the node j, and a (i, j) ═ 0 does not reach the node j from the node i. The specific value of A (i, j) is obtained by randomly generating a decimal between 0 and 1 and rounding. In a undirected network, undirected edges are considered to be bi-directionally reachable, i.e., a (i, j) ═ a (j, i), i.e., matrix a, is a symmetric matrix.
And II, continuously expanding the network by adding the nodes, and selecting the old nodes connected with the nodes by using the preferred connectivity as a criterion for each added node until the number of the nodes in the network reaches N. The preferential connection performance can ensure that the newly added node is preferentially connected to the old node with better connectivity. This is accomplished by generating probability values that match the connectivity of the nodes. Suppose that each new node needs to connect k old nodes (k being a given constant). Finally, a connected undirected scaleless network is generated, namely the directed graph is connected with the base graph, and the final directed graph is ensured to be weakly connected. The method for establishing connection for the new _ node at the ith time (i < ═ k) is as follows:
firstly, scanning the adjacency matrix, counting the degree of each node, and then constructing a numerical value interval matched with the degree of the node. For example, if three old nodes in the fixed network are a, b, and c, and their degrees are 2,8, and 4, respectively, it is necessary to construct a section with a total section length of 2+8+4 ═ 14 degrees, and each cell section is [1,2], [3,10], [11, and 14], respectively. In order to preferentially connect the newly added node to the old node with better connectivity, an integer r uniformly distributed in the interval [1,14] is randomly generated, and the r falls into one of the three intervals, and is assumed to fall into the interval range [11,14] corresponding to the third node, namely the c node. If the newly added node has not been connected with the third node, that is, the current a (new _ node, c) is 0, then the corresponding a (new _ node, c) and a (c, new _ node) are assigned to 1, and the selected neighbor is added with 1. Otherwise, if the selected point has passed the new _ node, it needs to continue to generate random numbers distributed in [1,14], and continue to select neighbors.
And III, after the network with the number of the nodes being N is generated, the distribution of all the node degrees in the network needs to be statistically solved. The specific method comprises the following steps: and counting the degree of each node, and then removing the duplication of the result, namely solving the number of the non-repetitive degrees appearing in the network. Then, the number of nodes corresponding to each degree is obtained through statistics, and the total number of the degrees is divided by the number, so that the distribution of the degrees is obtained. For example, if the degrees of five nodes in the network are 2,2,4,5,5, the degree of non-repetition is 2,4,5, the number of nodes falling in the 2,4,5 interval is 2,1,2, and the frequency of the degrees 2,4,5 is 0.4,0.2, 0.4.
And secondly, orienting the undirected edge by generating a topological sorting sequence of the network. Topological ordering is the process of linearizing a non-linear structure, and it arranges all nodes in a graph into a linear sequence, so that any pair of vertices u and v in the graph, if an edge (u, v) belongs to a directed graph G, then in the final linear sequence, node u must appear before node v. Conversely, if node u precedes node v in the sorted sequence, then if there is an edge between uv, the direction must be from node u to node v. The nature of the topological ordering ensures that the final directed graph is acyclic and that edges attached to points at the front of the sequence are predominantly directed away from the point and edges attached to points at the back of the sequence are predominantly directed toward the point. The invention firstly arranges the nodes in the network from small to large according to the illumination intensity, and then adjusts the sequence of the obtained nodes, wherein the adjustment aims to place the node with the largest degree at the middle of the sequence, so that the edges attached to the nodes with the largest degree have the emission and the incidence, and the entrance and the exit are as uniform as possible. And taking the final sequence as a topological ordering sequence, and orienting all the non-oriented edges at one time. The specific operation steps are as follows:
I. and counting the degrees of all nodes in the network, and sequencing all the nodes in sequence from small to large according to the illumination intensity. Wherein, the degree of a node is the number of edges attached to the node.
And II, adjusting the bit number of the node sequence with the degree from small to large generated in the above way, placing the node with the maximum degree in the middle, and placing the nodes with the large degree on two sides of the node sequence, namely, sequentially decreasing the degrees of the nodes from the middle to the two sides.
The resulting sequence is a topologically ordered sequence, which is used to orient all undirected edges. Assuming that the sequence has N nodes, and examining the edge emitted by the ith node in the sequence (i is more than or equal to 1 and less than or equal to N) each time in an iterative mode. Examine the ith node in turn i Node m in sequence following it m (m ranges from the (i + 1) th to the (N) th. (iv) a quinone i And a node m There is an undirected edge between them, so that when the edge is oriented, the direction of the edge is determined by the node i Is emitted to the node m . After the relations between all the (i + 1) th to Nth nodes and the ith node are considered in a circulating mode, the size of i is increased by 1 in an increasing mode, and all the emitted edges of the next node are oriented continuously. And sequentially circulating until i is equal to N +1, and finishing the whole process.
The entire second step is the key to the present invention. We illustrate the implementation of the invention. An example is given in fig. 4. FIG. 4(a) is a base graph of a directed graph that needs to be oriented, which can be seen to be connected. FIG. 4(b) is the bit sequence of the nodes sorted by the node degree. Wherein the size of the circle represents the size in degrees. Fig. 4(c) is the adjusted sequence. The node G with the largest degree is located in the middle, and the node E with the largest degree and the node F are located on two sides of the node G respectively. The nodes a and B of the smallest degree are at the beginning and end of the sequence in turn. When oriented with this sequence, taking the node G with the largest degree as an example, because G is connected to each node in the base graph, then three directed edges (A, G), (C, G) and (E, G) can be determined because three nodes of ACE are arranged before G. While FDB is ranked after G, (G, F), (G, D) and (G, B) can be determined. The resulting directed network is shown in fig. 4 (d).
Example 2
The specific implementation mode of the invention is as follows:
the first step is to create a small random network of m nodes and randomly determine whether undirected connections exist among the m nodes.
And secondly, sequentially adding new nodes into the network. And determining the connection relation between the new node and the k old nodes for each added new node. The method for establishing the ith (1 ═ i < k) connection is to count the degrees of all the old nodes to generate a total degree interval, wherein the interval corresponding to each old node is directly related to the degree of the old node. And if the connection between the new node and the old node corresponding to the section does not exist (namely A (new node, old node) in the two-dimensional matrix currently representing the node relationship is equal to 0), the A (new node, old node) is made to be A (old node, new node) equal to 1, and the next selection is continued. If a connection is already present, a new random number is regenerated and the trial is repeated.
And thirdly, sequencing the nodes in the network from small to large according to the degrees of the nodes, and then adjusting the sequence to enable the degrees of the nodes from the middle to the two ends to be sequentially reduced.
And fourthly, taking the sequence generated in the third step as a final topological sorting sequence to orient the undirected graph. Locating each node i in the sequence, scanning each node j following it in the sequence, and if there is an undirected edge in the base graph between i and j, the direction of the edge is directed from i to j. The complexity of the whole operation is O (n) 2 )。
And fifthly, determining all the non-edge directions, and ending the method.
The symbols and meanings of the present invention are shown in Table 1.
TABLE 1 description of symbols and meanings in the present invention
In the above embodiments, all or part may be implemented by software. When used in whole or in part, is implemented in a computer program product that includes one or more computer instructions. When loaded or executed on a computer, cause the flow or functions according to embodiments of the invention to occur, in whole or in part. The computer may be a general purpose computer, a special purpose computer, a network of computers, or other programmable device. The computer instructions may be stored in a computer readable storage medium or transmitted from one computer readable storage medium to another computer readable storage medium, for example, the computer instructions may be transmitted from one website, computer, server, or data center to another website, computer, server, or data center via wire (e.g., coaxial cable, fiber optic, Digital Subscriber Line (DSL), or wireless (e.g., infrared, wireless, microwave, etc.)). The computer-readable storage medium can be any available medium that can be accessed by a computer or a data storage device, such as a server, a data center, etc., that includes one or more of the available media. The usable medium may be a magnetic medium (e.g., floppy Disk, hard Disk, magnetic tape), an optical medium (e.g., DVD), or a semiconductor medium (e.g., Solid State Disk (SSD)), among others.
The above description is only for the purpose of illustrating the embodiments of the present invention, and the scope of the present invention should not be limited thereto, and any modifications, equivalents and improvements made by those skilled in the art within the technical scope of the present invention as disclosed in the present invention should be covered by the scope of the present invention.
Claims (10)
1. A method for generating a weakly connected directional loop-free scale-free network, the method comprising the steps of:
step one, a small random network of m nodes is established; wherein m is a given parameter, and m nodes are randomly connected;
step two, adding new nodes into the network one by one, and providing that each newly added node is connected with K nodes in the current network at most and preferentially connected with nodes with large numbers in the current network; repeating the step two until the number of the nodes in the network reaches a specified number | V |;
step three, judging whether the undirected graph is communicated, if so, executing a step five; otherwise, executing the step four;
step four, deleting the minimum connected component in the network, and executing the step two;
counting the degrees of all nodes in the network, and performing topological sorting on all nodes according to the sequence of the degrees from small to large;
step six, adjusting the sequencing sequence to ensure that the degrees of the nodes in the sequence are sequentially decreased from the middle to the two ends, and using the sequence as a final topology sequencing sequence of the directed network;
step seven, orienting the edges in the generated connected undirected small-world network one by one; deleting undirected edges (i, j) in the network, inspecting the bit order relationship between the nodes i and the nodes j in the topological sorting sequence, and adding directed edges to point to the nodes j from the nodes i if the nodes i are arranged in front of the nodes j; otherwise, adding a directed edge starting from the node j to the node i;
step eight, judging whether the orientation of all edges is finished, if so, finishing the process; otherwise, the step seven is continuously executed.
2. The method for generating a weakly-connected directed acyclic unscaled network according to claim 1, wherein in step two, the method for establishing the ith (1 ═ i < k) connection comprises:
counting the degrees of all the old nodes to generate a total degree interval, wherein the interval corresponding to each old node is directly related to the degree; randomly generating a random number r uniformly distributed in a degree interval, and inspecting whether a connection exists between a new node and an old node corresponding to the interval according to the interval in which r is distributed; if not, namely A (new node and old node) is 0 in the two-dimensional matrix currently representing the node relationship, then A (new node and old node) is made to be A (old node and new node) to be 1, and the next selection is continued; if a connection is already present, a new random number is regenerated and the probe is performed again.
3. The method of generating a weakly-connected directed acyclic unscaled network of claim 1, wherein the method of generating a weakly-connected directed acyclic unscaled network further comprises creating an undirected unscaled network with a number of nodes N; the creation process of the undirected scaleless network comprises the following steps:
(1) creating a small random network: setting the number of initial nodes in the small random network as M, and the number of nodes in the finally generated scale-free network as N, wherein M < < N; firstly, generating M nodes, then randomly generating the relationship among the M nodes, and storing the relationship among the nodes in the network by adopting an adjacency matrix A; a (i, j) ═ 1 represents that there is a directed edge between the node i and the node j, and a (i, j) ═ 0 cannot reach the node j from the node i; the value of A (i, j) is obtained by randomly generating a decimal between 0 and 1 and rounding; in a undirected network, an undirected edge is bi-directionally reachable, i.e., a (i, j) ═ a (j, i), i.e., matrix a, is a symmetric matrix;
(2) continuously expanding the network by adding nodes, and selecting old nodes connected with each added node by using preferred connectivity as a criterion for each added node until the number of nodes in the network reaches N; the preferential connection performance can ensure that the newly added node is preferentially connected to the old node with better connectivity, and the preferential connection performance is realized by generating a probability value matched with the connectivity of the nodes; assuming that each new node needs to connect k old nodes, k being a given constant; finally, generating a connected undirected scale-free network, namely, the connected base graphs of the directed graphs, and ensuring that the final directed graphs are weakly connected;
(3) after a network with the number of nodes being N is generated, counting and solving the distribution of all node degrees in the network; wherein, the statistical method comprises the following steps: counting the degree of each node, and then removing the duplication of the result, namely solving the number of the non-repeated degrees in the network; counting to obtain the number of nodes corresponding to each degree, and dividing the number by the total number of the degrees to obtain the distribution of the degrees; five nodes are arranged in the network, and the degrees of the nodes are 2,2,4,5 and 5 respectively; the non-repeating degree is 2,4,5, and the number of nodes falling in the interval of 2,4,5 is 2,1,2, respectively, so that the frequency of degree 2,4,5 is 0.4,0.2,0.4, respectively.
4. The method for generating a weakly-connected directed acyclic unscaled network according to claim 3, wherein in the step (2), the method for establishing a connection for the new node new _ node at the ith time (i < k) comprises:
firstly, scanning an adjacency matrix, counting the degree of each node, and then constructing a numerical interval matched with the degree of the node; if three old nodes in the fixed network are a, b and c, and their degrees are 2,8 and 4, respectively, it is necessary to construct an interval with a total interval length of 2+8+4 ═ 14 degrees, and each cell is [1,2], [3,10], [11 and 14 ]; in order to preferentially connect the newly added node to the old node with better connectivity, an integer r uniformly distributed in the interval [1,14] is randomly generated, the r falls into one of the three intervals, and the range of the interval [11,14] corresponding to the third, namely c node is supposed to fall into; if the newly added node is not connected with the third node at present, namely the current A (new _ node, c) is 0, the corresponding A (new _ node, c) and A (c, new _ node) are assigned to be 1, and the selected neighbor is added with 1; otherwise, if the selected point has passed the new _ node, continuing to generate the random numbers distributed in [1,14], and continuing to select the neighbor.
5. The method of generating a weakly-connected directed acyclic unscaled network according to claim 1, further comprising orienting the undirected edges by generating a topological ordered sequence of networks, comprising:
topological sorting is a process of linearizing a nonlinear structure, and all nodes in a graph are arranged into a linear sequence, so that if an edge (u, v) belongs to a directed graph G, a node u is always in front of the node v in a final linear sequence; conversely, if node u precedes node v in the sorted sequence, if there is an edge between uv, the direction must be from node u to node v; the nature of topological sorting can ensure that the final directed graph is acyclic, and the edge attached to the point at the front end of the sequence is mainly emitted from the point, and the edge attached to the point at the rear end of the sequence is mainly emitted to the point; arranging nodes in the network from small to large according to the illumination intensity, sequentially adjusting the obtained sequence, and placing the node with the largest degree at the middle of the sequence to ensure that the edges attached to the nodes with the large degree have ejection and ejection, and the in-out degree is uniform; and taking the final sequence as a topological ordering sequence, and orienting all the non-oriented edges at one time.
6. The method for generating a weakly-connected directed acyclic unscaled network according to claim 5, wherein said directing of undirected edges by generating a topologically ordered sequence of networks, further comprises the steps of:
(1) counting the degrees of all nodes in the network, and sequencing all the nodes in sequence from small to large according to the illumination intensity; wherein, the degree of the node is the number of the edges attached to the node;
(2) adjusting the number of bits of the node sequence with the generated degrees from small to large, placing the node with the maximum number of degrees in the middle, and placing the nodes with the large number of degrees on two sides of the node sequence, namely, sequentially decreasing the number of degrees of the nodes from the middle to the two sides;
(3) the finally obtained sequence is a topological sorting sequence, and all the undirected edges are oriented by using the topological sorting sequence; assuming that the sequence has N nodes, and in an iterative mode, the edge 1 emitted by the ith node in the sequence is not less than i and not more than N each time the sequence is examined; examine the ith node in turn i Node m in sequence following it m The value range of m is from the (i + 1) th to the N (N); if node i And a node m There is an undirected edge between them, so that when the edge is oriented, the direction of the edge is determined by the node i Shoot to the node m (ii) a After the relations between all the (i + 1) th to Nth nodes and the ith node are considered circularly, the size of i is increased by 1, and all the emitted edges of the next node are oriented continuously; and sequentially circulating until i is equal to N +1, and finishing the whole process.
7. A weakly-connected directed acyclic unscaled network generation system implementing the weakly-connected directed acyclic unscaled network generation method according to any one of claims 1 to 6, wherein the weakly-connected directed acyclic unscaled network generation system comprises:
the random network creating module is used for creating a small random network of m nodes and randomly determining whether undirected connection exists between the m nodes;
the node adding module is used for sequentially adding new nodes into the network and determining the connection relation between the new nodes and k old nodes for each added new node;
the node sequencing module is used for sequencing the nodes in the network from small to large according to the degrees of the nodes and adjusting the sequence to ensure that the degrees of the nodes from the middle part to the two ends are reduced in sequence;
the undirected graph orientation module is used for orienting the undirected graph by taking the generated sequence as a final topological sorting sequence, positioning each node i in the sequence and scanning each node j behind the node i in the sequence in turn; if an undirected edge exists between the node i and the node j in the base graph, the direction of the edge is shot to the node j by the node i; and ending when all the non-side directions are determined.
8. A computer arrangement comprising a memory and a processor, the memory storing a computer program which, when executed by the processor, causes the processor to carry out the steps of:
creating a small random network of m nodes, and randomly determining whether undirected connection exists between the m nodes; sequentially adding new nodes into the network, and determining the connection relation between the new nodes added each time and k old nodes; sequencing the nodes in the network from small to large according to the degrees of the nodes, and adjusting the sequence to ensure that the degrees of the nodes from the middle part to the two ends are reduced in sequence; taking the generated sequence as a final topological sorting sequence to orient the undirected graph, positioning each node i in the sequence, and scanning each node j behind the node i in the sequence in sequence; if there is an undirected edge in the base graph between i and j, the direction of the edge is from i to j, and the complexity of the whole operation is O (n) 2 ) (ii) a All the non-edgewise directions have been determined, the whole process ends.
9. A computer-readable storage medium storing a computer program which, when executed by a processor, causes the processor to perform the steps of:
creating a small random network of m nodes, and randomly determining whether undirected connection exists between the m nodes; sequentially adding new nodes into the network, and determining the connection relation between the new nodes added each time and k old nodes; the nodes in the network are ordered according to the degree of the nodes from small to large, and the sequence is adjusted to ensure thatThe degrees of the nodes from the middle part to the two ends are sequentially reduced; taking the generated sequence as a final topological sorting sequence to orient the undirected graph, positioning each node i in the sequence, and scanning each node j behind the node i in the sequence in turn; if there is an undirected edge between node i and node j in the base graph, the direction of the edge is shot from node i to node j, and the complexity of the whole operation is O (n) 2 ) (ii) a All the non-edgewise directions have been determined, the whole process ends.
10. An information data processing terminal characterized in that the information data processing terminal is used for realizing the weakly connected directed acyclic unscaled network generation system according to claim 7.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202110862087.3A CN113660116B (en) | 2021-07-29 | 2021-07-29 | Weak-communication directed acyclic scale-free network generation method |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202110862087.3A CN113660116B (en) | 2021-07-29 | 2021-07-29 | Weak-communication directed acyclic scale-free network generation method |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN113660116A CN113660116A (en) | 2021-11-16 |
| CN113660116B true CN113660116B (en) | 2022-07-26 |
Family
ID=78478965
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN202110862087.3A Active CN113660116B (en) | 2021-07-29 | 2021-07-29 | Weak-communication directed acyclic scale-free network generation method |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN113660116B (en) |
Families Citing this family (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN114124722B (en) * | 2021-11-22 | 2024-01-19 | 湖南经研电力设计有限公司 | Directed acyclic graph generation method, network coding method and network transmission method |
| CN115967631A (en) * | 2022-12-19 | 2023-04-14 | 天津大学 | Internet of things topology optimization method based on breadth learning and application thereof |
| CN119721877A (en) * | 2023-09-28 | 2025-03-28 | 华为技术有限公司 | Architecture diagram generation method and architecture diagram construction system |
Citations (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN101572961A (en) * | 2009-05-31 | 2009-11-04 | 北京航空航天大学 | Mobile scale-free self-organizing network model building method |
| CN101848557A (en) * | 2009-05-31 | 2010-09-29 | 北京航空航天大学 | Method for constructing mobile scale-free self-organized network model |
| CN102904815A (en) * | 2012-09-21 | 2013-01-30 | 中国电子科技集团公司第二十八研究所 | Route-Level Topology Modeling Method Based on Scale-Free Networks |
| CN111651683A (en) * | 2020-06-02 | 2020-09-11 | 重庆邮电大学 | A Scale-Free Network Generation Method with Adjustable Parameters |
| CN111934901A (en) * | 2020-06-24 | 2020-11-13 | 合肥工业大学 | Topology control method and system of unmanned platform information-aware network |
Family Cites Families (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US20070291663A1 (en) * | 2006-06-19 | 2007-12-20 | Nokia Corporation | Method and apparatus for scale-free topology generation in relay based wireless networks |
| US20100057902A1 (en) * | 2008-08-28 | 2010-03-04 | Novell, Inc. | Scal-free management networks |
| CN102185916B (en) * | 2011-04-27 | 2013-06-26 | 西安电子科技大学 | Method for establishing sensor network with small world and scale-free properties |
-
2021
- 2021-07-29 CN CN202110862087.3A patent/CN113660116B/en active Active
Patent Citations (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN101572961A (en) * | 2009-05-31 | 2009-11-04 | 北京航空航天大学 | Mobile scale-free self-organizing network model building method |
| CN101848557A (en) * | 2009-05-31 | 2010-09-29 | 北京航空航天大学 | Method for constructing mobile scale-free self-organized network model |
| CN102904815A (en) * | 2012-09-21 | 2013-01-30 | 中国电子科技集团公司第二十八研究所 | Route-Level Topology Modeling Method Based on Scale-Free Networks |
| CN111651683A (en) * | 2020-06-02 | 2020-09-11 | 重庆邮电大学 | A Scale-Free Network Generation Method with Adjustable Parameters |
| CN111934901A (en) * | 2020-06-24 | 2020-11-13 | 合肥工业大学 | Topology control method and system of unmanned platform information-aware network |
Also Published As
| Publication number | Publication date |
|---|---|
| CN113660116A (en) | 2021-11-16 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN113660116B (en) | Weak-communication directed acyclic scale-free network generation method | |
| US8914491B2 (en) | Assigning telecommunications nodes to community of interest clusters | |
| US20100027442A1 (en) | Constructing scalable overlays for pub-sub with many topics: the greedy join-leave algorithm | |
| Meiners et al. | Split: Optimizing space, power, and throughput for TCAM-based classification | |
| CN115297048B (en) | Routing path generation method and device based on optical fiber network | |
| Ren et al. | On efficient delay-aware multisource multicasting in NFV-enabled softwarized networks | |
| CN115102963A (en) | IP (Internet protocol) distinguishing method, storage medium and electronic equipment of neighbor nodes based on virtual currency public link network transaction nodes | |
| CN112711588B (en) | Method and device for multi-table connection | |
| Yadav et al. | CCTorus: A new torus topology for interconnection networks | |
| CN116718205A (en) | A path planning method based on the large-scale sparse Chinese postman problem | |
| Boukhalfa et al. | Network traffic analysis using big data and deep learning techniques | |
| CN117763214A (en) | Local community dynamic detection method and device, electronic equipment and storage medium | |
| Kong et al. | Deep reinforcement learning-based service function chains (SFCs) deployment | |
| Oloduowo et al. | Solving network routing problem using artificial intelligent techniques | |
| Guo et al. | DFed-SST: Building Semantic-and Structure-aware Topologies for Decentralized Federated Graph Learning | |
| CN119276725B (en) | Methods, apparatus, devices and storage media for recommending virtual network topologies | |
| Shim et al. | New center location algorithms for shared multicast trees | |
| Tajary et al. | A routing-aware simulated annealing-based placement method in wireless network on chips | |
| Zhang et al. | Graphlib: A parallel graph mining library for joint cloud computing | |
| Aggarwal et al. | Constrained diameter steiner trees for multicast conferences in overlay networks | |
| Ben-Asher et al. | 2-D SIMD algorithms for perfect shuffle networks | |
| Makki | A distributed algorithm for constructing an Eulerian tour | |
| Liu et al. | Benchmark snapshots for testing social network evolving algorithms | |
| Espínola | A New Community Detection Algorithm | |
| Moradi et al. | An Improved Multi-objective Genetic Algorithm for Revealing Community Structures of Complex Networks |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |