1. A computer-implemented method, comprising:
identifying one or more influences within a network, the identifying comprising:
representing the network as a graph comprising a plurality of nodes, the graph being further represented by an adjacency matrix;
multiplying a random probe vector vi by a resolvent function (A\u2212zI)\u22121, wherein A is the adjacency matrix, I is an identity matrix, and z is a selected scalar number
using a result of the multiplying the random probe vector by the resolvent function as an approximation of a product of a matrix exponential and the random probe vector;
computing, by a computer processor, a diagonal of the adjacency matrix based on the product of the matrix exponential and the random probe vector, wherein the computing comprises:
initializing vectors Q, W, and D of length N to zero, wherein the vector D represents the diagonal;
initializing the random probe vector vi;
computing the product of the matrix and the random probe vector;
updating the vector Q by calculating Q=Q+vi.\xd7Z, where Z is the product of the matrix and the random probe vector, wherein .x symbolizes element-wise multiplication;
updating the vector W by calculating W=W+vi.\xd7vi;
updating the vector D by calculating D=D+Q .W, wherein . symbolizes element-wise division; and
repeating the initializing the random probe vector, the computing the product, the updating the vector Q, the updating the vector W, and the updating the vector D until at least one of (a) the difference of a previously estimated diagonal and an estimated diagonal is smaller than a designated diagonal tolerance, and (b) a percentage of nodes with target centrality has converged; and
calculating node centralities of the graph based on the computed diagonal of the adjacency matrix.
2. The computer-implemented method of claim 1, wherein the approximating of the product of the matrix and the random probe vector further comprises:
computing an orthogonal Krylov basis and tridiagonal matrix, based on the adjacency matrix, using a Lanczos algorithm;
computing a matrix exponential of the tridiagonal matrix; and
computing a current approximation of the product of the matrix exponential and the random probe vector.
3. The method of claims 1, wherein the network is a social network, wherein identifying the one or more influencers within the network comprises identifying one or more influential people in the social network, and the method further comprising:
selecting one or more central nodes of the graph, based on the node centralities, representing the one or more influential people in the social network.
4. A computer program product comprising a non-transitory computer readable storage medium having program instructions embodied therewith, the program instructions executable by a processor to cause the processor to perform a method comprising:
identifying one or more influences within a network, the identifying comprising:
representing the network as a graph comprising a plurality of nodes, the graph being further represented by an adjacency matrix;
multiplying a random probe vector vi by a resolvent function (A\u2212zI)\u22121, wherein A is the adjacency matrix, I is an identity matrix, and z is a selected scalar number;
using a result of the multiplying the random probe vector by the resolvent function as an approximation of a product of a matrix exponential and the random probe vector;
computing a diagonal of the adjacency matrix based on the product of the matrix exponential and the random probe vector, wherein the computing comprises:
initializing vectors Q, W, and D of length N to zero, wherein the vector D represents the diagonal;
initializing the random probe vector vi;
computing the product of the matrix and the random probe vector;
updating the vector Q by calculating Q=Q+vi .x Z, where Z is the product of the matrix and the random probe vector, wherein .x symbolizes element-wise multiplication;
updating the vector W by calculating W=W+vi .x vi;
updating the vector D by calculating D=D+Q .W, wherein . symbolizes element-wise division; and
repeating the initializing the random probe vector, the computing the product, the updating the vector Q, the updating the vector W, and the updating the vector D until at least one of (a) the difference of a previously estimated diagonal and an estimated diagonal is smaller than a designated diagonal tolerance, and (b) a percentage of nodes with target centrality has converged; and
calculating node centralities of the graph based on the computed diagonal of the adjacency matrix.
5. The computer program product of claim 4, wherein the approximating of the product of the matrix and the random probe vector further comprises:
computing an orthogonal Krylov basis and tridiagonal matrix, based on the adjacency matrix, using a Lanczos algorithm;
computing a matrix exponential of the tridiagonal matrix; and
computing a current approximation of the product of the matrix exponential and the random probe vector.
6. The computer program product of claim 4, wherein the network is a social network, wherein identifying the one or more influencers within the network comprises identifying one or more influential people in the social network, and the method further comprising:
selecting one or more central nodes of the graph, based on the node centralities, representing the one or more influential people in the social network.
The claims below are in addition to those above.
All refrences to claim(s) which appear below refer to the numbering after this setence.
1. A method for buffering data in a network device, the method comprising the steps of:
initializing a plurality of output queues;
determining to which of the plurality of output queues data arriving at the network device is destined;
storing the data in one or more buffers, wherein the one or more buffers is selected from a data memory group including an internal data memory and an external data memory; and
enqueuing the one or more buffers to the destined output queue.
2. The method of claim 1, wherein:
the plurality of output queues are initialized by associating at least one output queue with the internal data memory and at least another output queue with the external data memory; and
the data is stored according to a static queuing scheme.
3. The method of claim 2, wherein the static queuing scheme includes:
storing the data in the one or more buffers of the data memory group to which the destined output queue is associated.
4. The method of claim 2, wherein the static queuing scheme includes:
storing the data in both an internal data memory location and an external data memory location; and
purging the data from the storage location to which the destined output queue is not associated.
5. The method of claim 2, wherein the static queuing scheme includes:
storing the data in only one of an internal data memory location and an external data memory location; and
moving the data from the storage location to which the destined output queue is associated if the destined output queue is associated with a different storage location.
6. The method of claim 2, wherein the static queuing scheme includes:
storing the data in an internal data memory location; and
moving the data from the internal data memory location to an external data memory location if the destined output queue is associated with the external data memory location.
7. The method of claim 2, wherein:
the data belongs to a class of datas, the class of datas including a multicast data, a broadcast data, a unicast data that is mirrored to at least two output queues, and a unicast data that is copied between at least two output queues;
the destined output queue includes the at least two queues; and
the one or more buffers includes at least one storage instance.
8. The method of claim 7, where in the plurality of output queues includes one or more of an internal queue, an external queue and an aggregate queue.
9. The method of claim 1, wherein:
the plurality of output queues are initialized to be capable of selectively choosing between the internal data memory and the external data memory;
the data is stored according to a dynamic queuing scheme.
10. The method of claim 9, wherein the dynamic queuing scheme includes, if both the internal data memory and the external data memory are available, choosing the internal data memory first and the external data memory second.
11. The method of claim 9, wherein the dynamic queuing scheme includes, if only one of the internal data memory and the external data memory is available, choosing the one available.
12. The method of claim 9, where in the plurality of output queues includes one or more of an internal queue, an external queue and an aggregate queue.
13. The method of claim 1, wherein the data memory is partitioned into a plurality of full-size data buffers.
14. The method of claim 1, wherein the data memory is partitioned into a plurality of cell-based buffers, each of a size less than a full-sized data.
15. The method of claim 14, wherein the one or more buffers includes at least two of the plurality of cell-based buffers.
16. A network device, the device comprising processing logic, wherein the processing logic is capable of:
initializing a plurality of output queues;
determining to which of the plurality of output queues a data arriving at the network device is destined;
storing the data in one or more buffers, wherein the one or more buffers is selected from a data memory group including an internal data memory and an external data memory; and
enqueuing the one or more buffers to the destined output queue.
17. The device of claim 16, wherein:
the plurality of output queues are initialized by associating at least one output queue with the internal data memory and at least another output queue with the external data memory; and
the data is stored according to a static queuing scheme.
18. The device of claim 17, wherein the static queuing scheme includes:
storing the data in the one or more buffers of the data memory group to which the destined output queue is associated.
19. The device of claim 17, wherein the static queuing scheme includes:
storing the data in both an internal data memory location and an external data memory location; and
purging the data from the storage location to which the destined output queue is not associated.
20. The device of claim 17, wherein the static queuing scheme includes:
storing the data in only one of an internal data memory location and an external data memory location; and
moving the data from the storage location to which the destined output queue is associated if the destined output queue is associated with a different storage location.
21. The device of claim 17, wherein:
the data belongs to a class of datas, the class of datas including a multicast data, a broadcast data, a unicast data that is mirrored to at least two output queues, and a unicast data that is copied between at least two output queues;
the destined output queue includes the at least two queues; and
the one or more buffers includes at least one storage instance.
22. The device of claim 21, where in the plurality of output queues includes one or more of an internal queue, an external queue and an aggregate queue.
23. The device of claim 16, wherein:
the plurality of output queues are initialized to be capable of selectively choosing between the internal data memory and the external data memory;
the data is stored according to a dynamic queuing scheme.
24. The device of claim 23, wherein the dynamic queuing scheme includes, if both the internal data memory and the external data memory are available, choosing the internal data memory first and the external data memory second.
25. The device of claim 23, wherein the dynamic queuing scheme includes, if only one of the internal data memory and the external data memory is available, choosing the one available.
26. The device of claim 23, where in the plurality of output queues includes one or more of an internal queue, an external queue and an aggregate queue.
27. The device of claim 16, wherein the data memory is partitioned into a plurality of full-size data buffers.
28. The device of claim 16, wherein the data memory is partitioned into a plurality of cell-based buffers, each of a size less than a full-sized data.
29. The device of claim 28, wherein the one or more buffers includes at least two of the plurality of cell-based buffers.