Detailed description of the invention
Embodiments herein is described below in detail, and the example of described embodiment is shown in the drawings, the most identical orSimilar label represents same or similar element or has the element of same or like function.Describe below with reference to accompanying drawingEmbodiment is exemplary, is only used for explaining the application, and it is not intended that restriction to the application.
In the description of the present application, it is to be understood that term " " center ", " longitudinally ", " laterally ", " on ", D score, " front ",Orientation or the position relationship of the instruction such as " afterwards ", "left", "right", " vertically ", " level ", " top ", " end ", " interior ", " outward " are baseIn orientation shown in the drawings or position relationship, it is for only for ease of description the application and simplifies description rather than instruction or hint instituteThe device that refers to or element must have specific orientation, with specific azimuth configuration and operation, therefore it is not intended that to the applicationRestriction.Additionally, term " first ", " second " are only used for describing purpose, and it is not intended that instruction or hint relative importance.
In the description of the present application, it should be noted that unless otherwise clearly defined and limited, term " install ", " being connected "," connect " and should be interpreted broadly, connect for example, it may be fixing, it is also possible to be to removably connect, or be integrally connected；PermissibleIt is to be mechanically connected, it is also possible to be electrical connection；Can be to be joined directly together, it is also possible to be indirectly connected to by intermediary, can be twoThe connection of individual element internal.For the ordinary skill in the art, can understand that above-mentioned term is in the application with concrete conditionIn concrete meaning.
Below with reference to the accompanying drawings random map generalization method and system according to the embodiment of the present application is described.
Fig. 1 is the flow chart of the random map generalization method according to one embodiment of the application.
As it is shown in figure 1, according to the random map generalization method of the embodiment of the present application, comprise the following steps.
S1, inputs original graph structure, and wherein, original graph structure includes N number of node, and wherein, N is positive integer.
Prototype structure figure in the embodiment of the present application can be arbitrary network graph structure, particularly complex network graph structure, such as,Neutral net graph structure, social networks graph structure and citation network graph structure etc. can be but not limited to.
After the initialization operation of S1, can generate, by S2-S7, the Random Graph that original graph structure is corresponding.The application'sIn one embodiment, (Bulk Synchronous Parallel Computing Model, Integral synchronous is counted parallel can to pass through BSPCalculate model) structure perform S2-S6 to generate Random Graph.
BSP structure is to be proposed in nineteen ninety by Valiant, and this model controls to coordinate based on a Master, multiple WorkerWorking machine synchronize perform, data from input queue read, the framework of this model as shown in Figure 2 a, wherein, Client clientEnd enters data into Worker, and notifies that Master starts working, and then waits that Master completes work, and from WorkerExtraction process terminate after data.Master receives the initiation message that Client client sends, and continuous iteration is not until enlivening(active) node is operated that (the Worker node first starting all active during this is operated, and waitsAll Worker update the quantity of the Worker of active after completing work), iteration notifies that Client completes task after completing.Worker is arranged to active state after the data receiving Client input, and then continuous iteration is until being inactive shapeState (first waits the initiation message that Master sends, then reads message from In-Q, and carry out Message Processing etc. during thisWork, and send message, and to whether being that active state is updated, notify that when iteration completes Master completes this and takes turnsIteration works), wherein, when there being message to be sent to Worker, Worker is arranged to active state.
BSP structure is not only a kind of architectural model, is also a kind of method of design concurrent program.BSP programming criterionBeing Integral synchronous (bulk synchrony), it is unique in that the introducing of superledge (super step) concept.One BSP program is sameTime there is the structure of two aspects of horizontal and vertical.From vertical, as shown in Figure 2 b, a BSP program is by a series of stringsSuperledge (super step) composition of row, this is similar to that a serial program structure.From level, in each superledge,All of task parallelism performs local calculation.
As shown in Figure 2 c, each superledge can be divided into the three below stage.
1) the local computing stage, the data in each processor only internal memory local to storage carry out local computing.
2) the global communication stage, any non-local data is operated (interactive operation).
3) fence synchronous phase, waits the end of all communication behaviors.
Thus, S2-S6 can be realized by superledge 0-4 of BSP structure respectively, specific as follows.
S2, selects M seed node among N number of node, and in M seed node, each node is chosen Q bar respectively and gone outLimit also generates Q bar first and goes out side information, and sends Q bar first respectively to any Q in addition to self other nodes respectivelyGo out side information, and Q bar is gone out limit locking.
In an embodiment of the application, among N number of node, select M seed node specifically include: by N number of jointPoint has the node on limit as seed node.Further, M seed node is chosen Q bar by below equation and is gone out limit:
Q=ceil (| Out (i) |/2) (1)
Wherein, what | Out (i) | was node i goes out limit quantity, and ceil () is the function that rounds up.
Specifically, step S2 can be realized by the superledge 0 in BSP structure, i.e. super step=0.
As super step=0, for each node in N number of node of original graph structure, if it exists limit, then may be usedUsing this node as seed node.Limit, and root is gone out from Q=ceil (| Out (i) |/2) bar that goes out to randomly select limit of each seed nodeGo out limit generation one first according to every and go out side information.Then Q bar first goes out side information be respectively sent to except first goes out limit letterBreath sends Q node outside node, that randomly select.Wherein, first go out side information include limit corresponding send nodeAnd peripheral node, be represented by [srcVertexId1, destVertexId1], wherein, srcVertexId1 be limit corresponding send jointPoint ID (Identity, identity), destVertexId1 is the peripheral node ID that limit is corresponding.
In embodiments herein, when inputting original graph structure, the original state on the limit in original graph structure is arranged to notThe value of lock-out state, i.e. limit is set to 0.When M seed node selects Q bar limit, and to except any Q of self fingerprintAfter other nodes individual occur Q bar first to go out side information respectively, the Q bar chosen can go out limit locking, the Q bar that will choose goes outThe value on limit is set to 1.
For example, for the prototype structure figure as shown in Figure 3 a inputted, there are 8 nodes, be respectively1,2,3,4,5,6,7,8, and 6 limits as shown in Figure 3 a.Wherein, node Isosorbide-5-Nitrae, 5,7,8 have limit, therefore, and node Isosorbide-5-Nitrae, 5,7,8Can be chosen for seed node, its quantity going out limit is respectively 1,1,1,1,2.Can obtain according to formula (1): node 1,4,5,7,8 canThe limit quantity that goes out selected is respectively 1,1,1,1,1.Then, as shown in Figure 3 b, illustrate as a example by node 8 and node 5,Limit can select one go out limit 8-> 5 from going out of node 8 at random, and generate this and go out the first of limit and go out side information [8,5] (dash-dotted gray lineRepresent transmission process), and send to any one node (such as sending to node 4) in addition to node 8, and by this 8-> 5The value on limit is set to 1, locks.Also limit can select one go out limit 5-> 2 from going out of node 5 at random, and generate this and go out limitFirst go out side information [5,2], and send to any one node (such as sending to node 6) in addition to node 5, and willThe value on this 5-> 2 limit is set to 1, locks.Wherein, locked limit grey filled lines represents.
S3, receives first and goes out the node of side information and go out side information according to receive first and judge whether to meet pre-in N number of nodeIf condition, as pre-conditioned in met, then from self selecting any bar go out limit and generate second and go out side information, and go out limit by secondInformation feeds back to send the first node going out side information.
In an embodiment of the application, N number of node receives the first node going out side information and goes out side information according to first and sentenceBreak and whether meet pre-conditioned specifically including: N number of node receives the first node going out side information and judges whether self hasLimit；If receiving the first node going out side information there is limit, then determine whether that the first peripheral node going out in side information isNo exist or from as the first peripheral node going out in side information in going out in limit of self；And if first go out the end in side informationPoint node does not exists in limit in going out of self and self is not that (destVertexId1 is not equal to the first peripheral node going out in side information4), then judgement meets pre-conditioned.
Specifically, step S3 can be realized by the superledge 1 in BSP structure, i.e. super step=1.
As super step=1, for each node in original graph structure, this super step=1 safeguards a List,For deposit this node all of go out limit, be the most i.e. called for short with List.If a node receives first and goes out side information, and shouldThere is limit in node, then judges that receive first goes out the destVertexId1 in side information [srcVertexId1, destVertexId1]Whether it is equal to this node ID at go out existence or the destVertexId1 in limit of this node.If destVertexId1 is at this nodeGo out in limit and do not exist, and destVertexId1 is not equal to the ID of this node, then sentence and meet condition, and select at random from ListTake a limit (the peripheral node ID on this unidirectional limit is destVertexId2), and (send to the node that ID is srcVertexId1First goes out sending of side information) transmission second goes out side information.
Wherein, second go out side information can include receiving first go out the node of side information from self select go out limit corresponding send jointPoint and peripheral node and first go out peripheral node included in side information, are represented by: [srcVertexId2,DestVertexId2, destVertexId1], wherein, srcVertexId2 is to receive the first node going out side information to select from selfGo out limit corresponding send node, destVertexId2 be receive first go out the node of side information from self select to go out limit correspondingPeripheral node, destVertexId1 is first to go out in side information included peripheral node.
For example, what Fig. 3 b interior joint 4 received that node 8 sends first goes out side information [8,5], and node 6 receives node 5First sent goes out side information [5,2], then node 4 and 6 judges whether self has limit respectively.Owing to node 6 does not go out limit,Then node 6 is unsatisfactory for pre-conditioned, and the conversion process of node 6 correspondence terminates.And node 4 has one to go out limit 4-> 3, and node4 receive first go out side information [8,5] send node not in this goes out limit 4-> 3, and node 4 is not first to go out side informationThe peripheral node of [8,5], therefore, node 4 meets pre-conditioned.
And then, as shown in Figure 3 c, randomly choose one of node 4 and go out limit 4-> 3, and generate second and go out side information [4,3,5],And what the node 4 receives first node 8 when going out side information sent, therefore, node 4 feeds back second to node 8 and goes out side information[4,3,5]。
S4, receives the second node going out side information and goes out side information according to second and generate the first exchange instruction and second in N number of nodeExchange instruction, and the second exchange instruction is sent to sending the second node going out side information.
In one embodiment of the invention, N number of node receives the second node going out side information and goes out side information life according to secondThe first exchange instruction and the second exchange instruction is become to specifically include: N number of node to receive the second node going out side information and checks selfGo out whether limit exists receive first go out the node of side information from self select go out peripheral node corresponding to limit or from asReceive first to go out the node of side information and go out, from self select, the peripheral node that limit is corresponding；And if receive first go out limit letterThe node of breath does not exists and self does not goes out side information for receiving described first from peripheral node corresponding to limit that go out self selectedNode from the peripheral node that limit is corresponding that goes out self selected, then generates the first exchange instruction and the second exchange instruction.
Wherein, the first exchange instruction and the second exchange instruction are changed sides for control, will the limit that go out of two nodes swap, byThis, although the limit of the network of generation there occurs change, but the out-degree of each node is still consistent with artwork structure with in-degree.Specifically, step S4 can be realized by the superledge 2 in BSP structure, i.e. super step=2.
As super step=2, for each node in original graph structure, if node srcVertexId1 receives feedbackSecond goes out side information for [srcVertexId2, destVertexId2, destVertexId1], then node srcVertexId1 checks that it goes out limitIn whether there is destVertexId2 node, and check whether node srcVertexId2 is destVertexId2 node, if nodeSrcVertexId1 go out limit does not exist destVertexId2 node and node srcVertexId2 and destVertexId2 node is notSame node, then start to exchange limit, it may be assumed that transmits the first exchange instruction [-, destVertexId1] and [+, destVertexId2] to nodeSrcVertexId1 (will the first exchange instruction be sent to oneself), and by the second exchange instruction [-, destVertexId2] and[+, destVertexId1] send to node srcVertexId2 (sending the second node going out side information).
For example, for shown in Fig. 3 c when node 8 receive second go out side information [4,3,5] time, node 8 checks node 8Go out whether limit exists and go out peripheral node corresponding to limit (i.e. going out the peripheral node 3 of limit 4-> 3) selected by node 4, due toThe limit that goes out of 8 is 8-> 6 and 8-> 5, there is not node 3, and node 4 is not same node with node 3, therefore, such as figureShown in 3d, the first exchange instruction [-, 5] and [+, 3] can be generated, and send to node 8, and generate the second exchange instruction [-, 3] and[+, 5], and send to node 4.
S5, receives the second node going out side information and performs the first exchange instruction, and the node receiving the second exchange instruction performs secondExchange instruction.
Specifically, step S5 can be realized by the superledge 3 in BSP structure, i.e. super step=3.
As super step=3, receive the second node (namely generating the node of the first exchange instruction) going out side information and performFirst exchange instruction, the node receiving the second exchange instruction performs the second exchange instruction.
For example, as shown in Figure 3 e, node 8 performs the first exchange instruction [-, 5] of oneself generating and [+, 3], i.e. deletes 8-> 5This edge adds 8-> 3 this edge simultaneously；Node 4 have received the second exchange instruction [-, 3] and [+, 5], then delete 4-> 3 this edgeAdd 4-> 5 this edge simultaneously.
All nodes are gone out limit and are unlocked by S6.
Specifically, step S6 can be realized by the superledge 4 in BSP structure, i.e. super step=4.
As super step=4, for each node, the value being gone out limit is set to 0, i.e. unlocks.For example, such as Fig. 3 fShown in, the value of the 5-of node 5 > 2 this edge is reseted and 0 is not unlocked (being become the black in Fig. 3 f from the Lycoperdon polymorphum Vitt in Fig. 3 e).
S7, it is judged that whether the execution number of times of step S2-S6 reaches to preset iterations, if reaching to preset iterations, then tiesBundle, otherwise repeated execution of steps S2-S6.
The most constantly repeat above superledge super step0-4, when performing number of times and reaching to preset iterations, terminate, andOutput performs the graph structure obtained for the last time.
Thus, by the executed in parallel local calculation strategy in superledge respectively to the task in step each in S2-S6 atReason, repeats through successive ignition, the execution time that can be substantially reduced, it is achieved the time complexity of minute rank, and can be significantlyThe load capacity of the amount of transmitted information during increase execution such that it is able to the task in the data volume of 1,000,000,000 ranks that realizes processes.
Wherein, presetting iterations PN can be: PN=n*M, wherein, M is the quantity on limit in original graph structure, and n is the most wholeNumber.Experiment proves that, the graph structure generated when n is 100 is fully random.
The random map generalization method of the embodiment of the present application, by arbitrarily selecting two limits from original graph structure, and ties in original graphThe node that sends that there is not Article 1 limit in structure sends node and second to the limit of the end node on Article 2 limit and Article 1 limitWhen the end node on bar limit is not same node, will Article 1 limit and Article 2 edge contract, and add sending by Article 1 limitNode to the limit of the end node on Article 2 limit and is sent the node limit to the end node on Article 1 limit, with right by Article 2 limitOriginal graph structure is changed sides, the process on final election limit of laying equal stress on-change sides, until performing to preset iterations, it is possible to obtain withOriginal graph structure node number, limit number are consistent, and the Random Graph that the out-degree of each node is the most consistent with in-degree.
Additionally, in each repetitive process select the task in limit-change sides all can executed in parallel, greatly reduce the execution time,After successive ignition, time complexity is also only a minute level.And parallel processing can be greatly increased the information during execution and passThe load capacity of the amount of passing such that it is able to the task in the data volume of 1,000,000,000 ranks that realizes processes.Relative to traditional Random Graph generation sideMethod, greatly reduces the storage capacity of time complexity and graph structure, and the Random Graph of big data quantity graph structure of being more convenient for generates.
In order to realize above-described embodiment, the application also proposes a kind of random map generalization system.
Fig. 4 is the structural representation of the random map generalization system according to one embodiment of the application.
As shown in Figure 4, according to the random map generalization system of the embodiment of the present application, including: input equipment 10 with control device20。
Specifically, input equipment 10 is used for inputting original graph structure, and wherein, original graph structure includes N number of node, wherein,N is positive integer.
Prototype structure figure in the embodiment of the present application can be arbitrary network graph structure, particularly complex network graph structure, such as,Neutral net graph structure, social networks graph structure and citation network graph structure etc. can be but not limited to.
Control device 20 to be used for controlling N number of node repeated execution of steps S2-S6, until it reaches default iterations terminates.
In an embodiment of the application, controlling device 20 can be by the superledge of Integral synchronous parallel computational model BSP structure0-4 realizes step S2-S6 to generate Random Graph.More specifically, control device 20 constantly repeat above superledge super step0-4,To repeat S2-S6, when performing number of times and reaching to preset iterations, terminate, and export the figure performing for the last time to obtainStructure, as the Random Graph generated.
BSP structure is to be proposed in nineteen ninety by Valiant, and this model controls to coordinate based on a Master, multiple WorkerWorking machine synchronize perform, data from input queue read, the framework of this model as shown in Figure 2 a, wherein, Client clientEnd enters data into Worker, and notifies that Master starts working, and then waits that Master completes work, and from WorkerExtraction process terminate after data.Master receives the initiation message that Client client sends, and continuous iteration is not until enlivening(active) node is operated that (the Worker node first starting all active during this is operated, and waitsAll Worker update the quantity of the Worker of active after completing work), iteration notifies that Client completes task after completing.Worker is arranged to active state after the data receiving Client input, and then continuous iteration is until being inactive shapeState (first waits the initiation message that Master sends, then reads message from In-Q, and carry out Message Processing etc. during thisWork, and send message, and to whether being that active state is updated, notify that when iteration completes Master completes this and takes turnsIteration works), wherein, when there being message to be sent to Worker, Worker is arranged to active state.
BSP structure is not only a kind of architectural model, is also a kind of method of design concurrent program.BSP programming criterionBeing Integral synchronous (bulk synchrony), it is unique in that the introducing of superledge (super step) concept.One BSP program is sameTime there is the structure of two aspects of horizontal and vertical.From vertical, as shown in Figure 2 b, a BSP program is by a series of stringsSuperledge (super step) composition of row, this is similar to that a serial program structure.From level, in each superledge,All of task parallelism performs local calculation.
As shown in Figure 2 c, each superledge can be divided into the three below stage.
1) the local computing stage, the data in each processor only internal memory local to storage carry out local computing.
2) the global communication stage, any non-local data is operated (interactive operation).
3) fence synchronous phase, waits the end of all communication behaviors.
Thus, by the executed in parallel local calculation strategy in superledge respectively to the task in step each in S2-S6 atReason, repeats through successive ignition, the execution time that can be substantially reduced, it is achieved the time complexity of minute rank, and can be significantlyThe load capacity of the amount of transmitted information during increase execution such that it is able to the task in the data volume of 1,000,000,000 ranks that realizes processes.
Wherein, presetting iterations PN can be: PN=n*M, wherein, M is the quantity on limit in original graph structure, and n is the most wholeNumber.Experiment proves that, the graph structure generated when n is 100 is fully random.
Wherein, S2, selecting M seed node among N number of node, in M seed node, each node is chosen respectivelyQ bar goes out limit and generates Q bar first and go out side information, and sends Q respectively to any Q in addition to self other nodes respectivelyBar first goes out side information, and Q bar goes out limit locking.
In an embodiment of the application, when control device selects M seed node among N number of node, specifically useIn: N number of node will have the node on limit as seed node, and specifically for controlling M seed node by followingFormula is chosen Q bar and is gone out limit:
Q=ceil (| Out (i) |/2) (1)
Wherein, what | Out (i) | was node i goes out limit quantity, and ceil () is the function that rounds up.
More specifically, step S2 can be realized by the superledge 0 in BSP structure, i.e. super step=0.
As super step=0, for each node in N number of node of original graph structure, if it exists limit, then may be usedUsing this node as seed node.Limit, and root is gone out from Q=ceil (| Out (i) |/2) bar that goes out to randomly select limit of each seed nodeGo out limit generation one first according to every and go out side information.Then Q bar first goes out side information be respectively sent to except first goes out limit letterBreath sends Q node outside node, that randomly select.Wherein, first go out side information include limit corresponding send nodeAnd peripheral node, be represented by [srcVertexId1, destVertexId1], wherein, srcVertexId1 be limit corresponding send jointPoint ID (Identity, identity), destVertexId1 is the peripheral node ID that limit is corresponding.
In embodiments herein, when inputting original graph structure, the original state on the limit in original graph structure is arranged to notThe value of lock-out state, i.e. limit is set to 0.When M seed node selects Q bar limit, and to except any Q of self fingerprintAfter other nodes individual occur Q bar first to go out side information respectively, the Q bar chosen can go out limit locking, the Q bar that will choose goes outThe value on limit is set to 1.
For example, for the prototype structure figure as shown in Figure 3 a inputted, there are 8 nodes, be respectively1,2,3,4,5,6,7,8, and 6 limits as shown in Figure 3 a.Wherein, node Isosorbide-5-Nitrae, 5,7,8 have limit, therefore, and node Isosorbide-5-Nitrae, 5,7,8Can be chosen for seed node, its quantity going out limit is respectively 1,1,1,1,2.Can obtain according to formula (1): node 1,4,5,7,8 canThe limit quantity that goes out selected is respectively 1,1,1,1,1.Then, as shown in Figure 3 b, illustrate as a example by node 8 and node 5,Limit can select one go out limit 8-> 5 from going out of node 8 at random, and generate this and go out the first of limit and go out side information [8,5] (dash-dotted gray lineRepresent transmission process), and send to any one node (such as sending to node 4) in addition to node 8, and by this 8-> 5The value on limit is set to 1, locks.Also limit can select one go out limit 5-> 2 from going out of node 5 at random, and generate this and go out limitFirst go out side information [5,2], and send to any one node (such as sending to node 6) in addition to node 5, and willThe value on this 5-> 2 limit is set to 1, locks.Wherein, locked limit grey filled lines represents.
S3, N number of node receive first go out the node of side information and go out side information according to receive first and judge whether to meet pre-If condition, as pre-conditioned in met, then from self selecting any bar go out limit and generate second and go out side information, and go out limit by secondInformation feeds back to send the first node going out side information.
In an embodiment of the application, control device 20 and receive the first node going out side information in controlling N number of nodeAccording to first go out side information judge whether to meet pre-conditioned time, specifically for: N number of node receives first and goes out side informationNode judges whether self has limit；If receiving the first node going out side information there is limit, then determine whether firstGo out whether the peripheral node in side information exists in limit or from as the first peripheral node going out in side information in going out of self；AndIn going out of self if first goes out peripheral node in side information limit does not exists and self it is not the first terminal going out in side informationNode (destVertexId1 is not equal to 4), then judgement meets pre-conditioned.
More specifically, step S3 can be realized by the superledge 1 in BSP structure, i.e. super step=1.
As super step=1, for each node in original graph structure, this super step=1 safeguards a List,For deposit this node all of go out limit, the most i.e. useListIt is called for short.If a node receives first and goes out side information, and shouldThere is limit in node, then judges that receive first goes out the destVertexId1 in side information [srcVertexId1, destVertexId1]Whether it is equal to this node ID at go out existence or the destVertexId1 in limit of this node.If destVertexId1 is at this nodeGo out in limit and do not exist, and destVertexId1 is not equal to the ID of this node, then sentence and meet condition, and select at random from ListTake a limit (the peripheral node ID on this unidirectional limit is destVertexId2), and (send to the node that ID is srcVertexId1First goes out sending of side information) transmission second goes out side information.
Wherein, second go out side information can include receiving first go out the node of side information from self select go out limit corresponding send jointPoint and peripheral node and first go out peripheral node included in side information, are represented by: [srcVertexId2,DestVertexId2, destVertexId1], wherein, srcVertexId2 is to receive the first node going out side information to select from selfGo out limit corresponding send node, destVertexId2 be receive first go out the node of side information from self select to go out limit correspondingPeripheral node, destVertexId1 is first to go out in side information included peripheral node.
For example, what Fig. 3 b interior joint 4 received that node 8 sends first goes out side information [8,5], and node 6 receives node 5First sent goes out side information [5,2], then node 4 and 6 judges whether self has limit respectively.Owing to node 6 does not go out limit,Then node 6 is unsatisfactory for pre-conditioned, and the conversion process of node 6 correspondence terminates.And node 4 has one to go out limit 4-> 3, and node4 receive first go out side information [8,5] send node not in this goes out limit 4-> 3, and node 4 is not first to go out side informationThe peripheral node of [8,5], therefore, node 4 meets pre-conditioned.
And then, as shown in Figure 3 c, randomly choose one of node 4 and go out limit 4-> 3, and generate second and go out side information [4,3,5],And what the node 4 receives first node 8 when going out side information sent, therefore, node 4 feeds back second to node 8 and goes out side information[4,3,5]。
S4, N number of node receive the second node going out side information go out side information according to second and generate the first exchange instruction and secondExchange instruction, and the second exchange instruction is sent to sending the second node going out side information.
In one embodiment of the invention, control device 20 and receive the second node going out side information in controlling N number of nodeAccording to second go out side information generate the first exchange instruction and the second exchange instruction time, specifically for: N number of node receives secondGo out the going out whether to exist in limit and receive first and go out the node of side information and go out limit from what self selected of node inspection self of side informationCorresponding peripheral node or from going out the node of side information and go out, from self select, the peripheral node that limit is corresponding as receiving first；WithAnd if receiving first and go out the node of side information and do not exist and self is not for connecing from peripheral node corresponding to limit that go out self selectedReceive described first and go out the node of side information from the peripheral node that limit is corresponding that goes out self selected, then generate the first exchange instruction andTwo exchange instructions.
Wherein, the first exchange instruction and the second exchange instruction are changed sides for control, will the limit that go out of two nodes swap, byThis, although the limit of the network of generation there occurs change, but the out-degree of each node is still consistent with artwork structure with in-degree.Specifically, step S4 can be realized by the superledge 2 in BSP structure, i.e. super step=2.
As super step=2, for each node in original graph structure, if node srcVertexId1 receives feedbackSecond goes out side information for [srcVertexId2, destVertexId2, destVertexId1], then node srcVertexId1 checks that it goes out limitIn whether there is destVertexId2 node, and check whether node srcVertexId2 is destVertexId2 node, if nodeSrcVertexId1 go out limit does not exist destVertexId2 node and node srcVertexId2 and destVertexId2 node is notSame node, then start to exchange limit, it may be assumed that transmits the first exchange instruction [-, destVertexId1] and [+, destVertexId2] to nodeSrcVertexId1 (will the first exchange instruction be sent to oneself), and by the second exchange instruction [-, destVertexId2] and[+, destVertexId1] send to node srcVertexId2 (sending the second node going out side information).
For example, for shown in Fig. 3 c when node 8 receive second go out side information [4,3,5] time, node 8 checks node 8Go out whether limit exists and go out peripheral node corresponding to limit (i.e. going out the peripheral node 3 of limit 4-> 3) selected by node 4, due toThe limit that goes out of 8 is 8-> 6 and 8-> 5, there is not node 3, and node 4 is not same node with node 3, therefore, such as figureShown in 3d, the first exchange instruction [-, 5] and [+, 3] can be generated, and send to node 8, and generate the second exchange instruction [-, 3] and[+, 5], and send to node 4.
The node that S5, reception second go out side information performs the first exchange instruction, and the node receiving the second exchange instruction performs secondExchange instruction.
More specifically, step S5 can be realized by the superledge 3 in BSP structure, i.e. super step=3.
As super step=3, receive the second node (namely generating the node of the first exchange instruction) going out side information and performFirst exchange instruction, the node receiving the second exchange instruction performs the second exchange instruction.
For example, as shown in Figure 3 e, node 8 performs the first exchange instruction [-, 5] of oneself generating and [+, 3], i.e. deletes 8-> 5This edge adds 8-> 3 this edge simultaneously；Node 4 have received the second exchange instruction [-, 3] and [+, 5], then delete 4-> 3 this edgeAdd 4-> 5 this edge simultaneously.
S6, all nodes are gone out limit it is unlocked.
More specifically, step S6 can be realized by the superledge 4 in BSP structure, i.e. super step=4.
As super step=4, for each node, the value being gone out limit is set to 0, i.e. unlocks.For example, such as Fig. 3 fShown in, the value of the 5-of node 5 > 2 this edge is reseted and 0 is not unlocked (being become the black in Fig. 3 f from the Lycoperdon polymorphum Vitt in Fig. 3 e).
The random map generalization system of the embodiment of the present application, by arbitrarily selecting two limits from original graph structure, and ties in original graphThe node that sends that there is not Article 1 limit in structure sends node and second to the limit of the end node on Article 2 limit and Article 1 limitWhen the end node on bar limit is not same node, will Article 1 limit and Article 2 edge contract, and add sending by Article 1 limitNode to the limit of the end node on Article 2 limit and is sent the node limit to the end node on Article 1 limit, with right by Article 2 limitOriginal graph structure is changed sides, the process on final election limit of laying equal stress on-change sides, until performing to preset iterations, it is possible to obtain withOriginal graph structure node number, limit number are consistent, and the Random Graph that the out-degree of each node is the most consistent with in-degree.
Additionally, in each repetitive process select the task in limit-change sides all can executed in parallel, greatly reduce the execution time,After successive ignition, time complexity is also only a minute level.And parallel processing can be greatly increased the information during execution and passThe load capacity of the amount of passing such that it is able to the task in the data volume of 1,000,000,000 ranks that realizes processes.Relative to traditional Random Graph generation sideMethod, greatly reduces the storage capacity of time complexity and graph structure, and the Random Graph of big data quantity graph structure of being more convenient for generates.
Any process described otherwise above or method describe and are construed as in flow chart or at this, represent include one orThe module of code, fragment or the part of the executable instruction of the more steps for realizing specific logical function or process, andThe scope of the preferred implementation of the application includes other realization, wherein can not be by order that is shown or that discuss, including rootAccording to involved function by basic mode simultaneously or in the opposite order, performing function, this should be by embodiments herein instituteBelong to those skilled in the art to be understood.
Represent in flow charts or the logic described otherwise above at this and/or step, for example, it is possible to be considered as realityThe sequencing list of the executable instruction of existing logic function, may be embodied in any computer-readable medium, holds for instructionRow system, device or equipment (system such as computer based system, including processor or other can from instruction execution system,Device or equipment instruction fetch also perform the system of instruction) use, or combine these instruction execution systems, device or equipment and use.For the purpose of this specification, " computer-readable medium " can be any can comprise, store, communicate, propagate or transmission procedure withFor instruction execution system, device or equipment or combine these instruction execution systems, device or equipment and device.ComputerThe more specifically example (non-exhaustive list) of computer-readable recording medium includes following: have the electrical connection section (electricity of one or more wiringSub-device), portable computer diskette box (magnetic device), random access memory (RAM), read only memory (ROM),Erasable edit read only memory (EPROM or flash memory), fiber device, and the read-only storage of portable optic diskDevice (CDROM).It addition, computer-readable medium can even is that and can print the paper of described program thereon or other are suitableMedium, because then can carry out editing, interpreting or if desired with it such as by paper or other media are carried out optical scanningHis suitable method is processed to electronically obtain described program, is then stored in computer storage.
Should be appreciated that each several part of the application can realize by hardware, software, firmware or combinations thereof.In above-mentioned enforcementIn mode, multiple steps or method can be with storing the software or firmware that in memory and be performed by suitable instruction execution systemRealize.Such as, if realized with hardware, with the most the same, available following technology well known in the artIn any one or their combination realize: have and patrol for the discrete of logic gates that data signal is realized logic functionCollect circuit, there is the special IC of suitable combination logic gate circuit, programmable gate array (PGA), field-programmableGate array (FPGA) etc..
Those skilled in the art are appreciated that realizing all or part of step that above-described embodiment method carries is canCompleting instructing relevant hardware by program, described program can be stored in a kind of computer-readable recording medium, shouldProgram upon execution, including one or a combination set of the step of embodiment of the method.
Additionally, each functional unit in each embodiment of the application can be integrated in a processing module, it is also possible to be eachUnit is individually physically present, it is also possible to two or more unit are integrated in a module.Above-mentioned integrated module is the most permissibleThe form using hardware realizes, it would however also be possible to employ the form of software function module realizes.If described integrated module is with software meritCan the form of module realize and as independent production marketing or when using, it is also possible to be stored in the storage of embodied on computer readable and be situated betweenIn matter.
Storage medium mentioned above can be read only memory, disk or CD etc..
In the description of this specification, reference term " embodiment ", " some embodiments ", " example ", " concrete example ",Or specific features, structure, material or the feature that the description of " some examples " etc. means to combine this embodiment or example describes comprisesIn at least one embodiment or example of the application.In this manual, the schematic representation to above-mentioned term not necessarily refers toIt is identical embodiment or example.And, the specific features of description, structure, material or feature can at any one orMultiple embodiments or example combine in an appropriate manner.
While there has been shown and described that embodiments herein, it will be understood by those skilled in the art that: without departing from thisThese embodiments can be carried out multiple change in the case of the principle of application and objective, revise, replace and modification, the application'sScope is limited by claim and equivalent thereof.