Questions tagged [network-analysis]
The network-analysis tag has no usage guidance.
44
questions
0
votes
0
answers
36
views
Two competing notions of average shortest path length?
Recently, I came across an article by Simon Dreyer, Antoine Genitrini and Mehdi Naima about two notions of average shortest path length...
Imagine a connected graph $G$ with n nodes.
Notion A To ...
- 103
0
votes
0
answers
18
views
Need citation or reference
"Real-world networks are usually sparsely connected"- can anyone provide some reference for this claim.
- 1
1
vote
1
answer
50
views
BFS on directed graph with disjointed edges?
There is a graph (directed and unweighted) and a collection of nodes. If I want to find a tree that has all those nodes in it and potentially some other ones as well, would BFS be a good algorithm to ...
- 11
0
votes
0
answers
21
views
how does weighted shortest distance modifies if two nodes are made into one
Let us say I have a bipartite network with developer and projects and nodes . And let the weights of network be the inverse of number of contributions. Say I already have computed the shortest ...
- 1
0
votes
1
answer
13
views
Relationship between Katz centrality and degree
Given an undirected graph, we know that the PageRank centrality without damping factor is proportional to the vertex degrees. Is that also true for Katz centrality?
- 101
1
vote
2
answers
61
views
Path Through Graph That Minimizes Node Attributes
I have a directed graph (DAG) containing many nodes, all with various attributes (node attributes not edge attributes). I have a single target (finish) node and a set of source (start) nodes. I want ...
- 11
1
vote
1
answer
181
views
The modularity difference in Louvain algorithm for community detection in graphs
I am interested in the formula of modularity difference between two partitions considered in the Louvain algorithm for community detection in graphs. I give a formal expression of this question below.
...
- 653
0
votes
1
answer
347
views
What's wrong in this network topology?
What are the six mistakes that were made in the configuration of the following network?
I could only find 3. Since the subnet on the left has 192.168.10.33 as ...
- 181
0
votes
0
answers
83
views
Can anyone please help me understand the definition of Store-and-Forward delay from the Kurose and Ross Networking Book?
I have gone through the questions related to store-and-forward and transmission delays but they didn't answer my question. My question is directly related to one of the excerpts in the book (Computer ...
- 101
1
vote
1
answer
146
views
Efficient Network Clustering Algorithm for Million Node Networks
I am looking for a clustering algorithm that is scalable up to large sparse undirected, unweighted networks (10-40M nodes, 10-80M edges). The most important aspects I care about are scaling efficiency ...
- 213
0
votes
1
answer
109
views
Go back n on server side
I am implementing a UDP based go back n example and I am a bit stuck on how the server should respond to packets.
If my client has a sliding window of say 5, it can send 5 packets to the server ...
- 115
0
votes
0
answers
73
views
Score and bound in Goemans-Williamson algorithm
I am trying to have a deeper understanding of the following implementation of the Goemans-Williamson algorithm for solving the maxcut problem.
...
- 326
2
votes
0
answers
111
views
Does minimumm spanning tree always include the node with highest degree?
I want to know why the distances between nodes in a minimum spanning tree seems to be rooted to the node with highest degree.
A bit of context here:
I have spatial explicit weighted network that ...
- 21
2
votes
2
answers
3k
views
Partitioning a graph into subgraphs with overlapping nodes
I'd like to partition a graph into subgraphs with overlapping nodes.
To do a simple partition into two, I could use kernighan_lin_bisection algorithm available in ...
- 71
1
vote
1
answer
124
views
how to reduce the time complexity of this code?
I have a graph G=(V,E). A list of nodes NODE subset of V. I want to find out all the ...
- 25
1
vote
1
answer
46
views
Source and Destination IP of TCP connection
Five Tuple Identifier of TCP connection is (TCP, local IP, local port, remote IP, remote port).
I have made 3 computers in virtual box and set BOX1 for client, BOX2 for median, and BOX3 for server. ...
5
votes
2
answers
506
views
Algorithm for finding "mean center" of unweighted graph
I have a large sparse unweighted undirected graph (20M vertices, 60M edges) and would like to find what I'm calling the "mean center" (the vertex w/ shortest mean distance to all other vertices. Does ...
- 213
0
votes
0
answers
9
views
What is the average time for a node to transmit on the shared medium for Ethernet? (IEEE 802.3)
Suppose a shared ethernet link L, in which for nodes T1-T4 and a router R are connected:
...
- 167
0
votes
1
answer
324
views
How to find the shortest route between (0,0) and (4,4) in a 5x5 matrix, given one horizontal or vertical translation per step
Consider the following matrix:
Input:
The entire list of coordinates ranging from (0,0) to (4,4).
A list indicating certain coordinates which cannot be used to generate a path reached.
So,
each ...
- 103
0
votes
1
answer
703
views
PERT Chart exercise - is there enough information to solve?
I'm posting this here as my question is from a computer science textbook. It is not a homework question as I am self-studying and I have the answers available.
In the exercise below, I can't see how ...
- 255
2
votes
1
answer
363
views
Finding maximal and average number of time slots in an Adaptive tree walk protocol
Tried to research here and on other sites with no luck regarding finding the maximal and average number of time slots in an Adaptive tree walk protocol. i'll explain what i mean here:
In a simple(...
- 21
3
votes
2
answers
395
views
Correctness of the Betweenness centrality formula
Betweenness centrality is defined as the number of shortest paths that go through a node in the graph.The formula is:
$$\sum_{s \neq v \neq t} \frac{\sigma_{st}(v)}{\sigma_{st}}$$
Where $\sigma_{st}$ ...
- 193
0
votes
0
answers
253
views
utilization of bitmap protocol
I am curious about utilization calculation in the bitmap protocol. especially if there's a difference between if only station 0 wants to broadcast(and the others doesn't) or only some other station ...
- 101
0
votes
0
answers
31
views
Affects of altering a line in "stop and wait" protocol(no noises)
what will happen if we change "to_physical_layer(&s)" to "to_physical_layer(&r)" in the following code(marked in the code where)?
does it make the protocol fail? if so, show a scenario it ...
- 1
1
vote
1
answer
33
views
Analyzing the railways network [closed]
I am studying complex networks and I have a question. Is it possible to use the tools and methods of the theory of complex network to study the properties of railways network? Are there any articles ...
2
votes
1
answer
51
views
(Formal) Proofs of Node Centrality Properties
Despite there being relatively frequent discourse regarding the usage and effectiveness of various node centralities when analysing the influential spreaders of a graph, I have thus far struggled to ...
- 23
2
votes
1
answer
42
views
Travelling Problem with Constraints
Consider a network with $N$ nodes $1,...,n$. Every node is connected to every node via a weighted edge, where the weight represents distance.
You start your travel at a given node, say $1$, and end ...
- 23
1
vote
2
answers
32
views
Representing a network with two types of connections: A fishing application
I want to represent a fishing network using a graph representation. My question surrounds how I can write the adjacency matrix if there are two types of connections, which I want to capture together.
...
1
vote
0
answers
489
views
How can node2vec help find similar "roles" within a graph (nodes whose connections have similar structure within the graph)?
I have a question on the node2vec algorithm described in this paper.
Node2vec is a deep learning algorithm that word2vec to graphs to learn embeddings. The authors claim that it can help find nodes ...
- 11
2
votes
0
answers
336
views
What is the difference between multi-layer, multiplex and heterogeneous networks?
I know when we have multiple networks connected to each other, we can call every network a layer and the whole network is called multi-layer. But I don't know what is the difference between multi-...
- 173
1
vote
0
answers
16
views
reference to model a network which nodes handle processing
does anybody have a basic reference (if it is possible) that explain how to mathematically model the state of a network. I assume that it goes like modeling a graph that is composed by nodes and edges....
- 121
0
votes
0
answers
64
views
Changes in prefix/ASN (Autonomous System Number) pairs?
I am wondering if a pair prefix/AS may change often ?
I mean let's say we have a list with many given prefixes (e.g. 4.6.20.0/24) that are mapped to ASN (e.g. 10753), this list is built on a given ...
2
votes
0
answers
35
views
Are exponential random graph models based on Maximum Entropy Principle?
Can anyone shed light on whether or not ERGMs are network models based on the maximum entropy principle? Especially if we say that the available information about the network is in the form of network ...
- 141
5
votes
1
answer
78
views
Sample a scale free subnet from random network
I already have a network which is like random complex network. Is there any way I can delete some of nodes and reduce the network into a scale-free network?
I notice there are some methods that can ...
- 51
2
votes
2
answers
589
views
Removing edges from a fully connected weighted graph
Given a fully connected graph $G(V,E)$ with associated edge weights and a set of constraints specifying distance $D(V_i, V_j) < M_{ij}$, where $\left\{V_{i..j}\right\} ⊂ V$, how can I go about ...
- 35
1
vote
0
answers
69
views
Identify community in a direct graph
I'm trying to identify communities in a direct graph.
I only know how to use Spectral clustering and Girvan-Newman method but the both the methods work only with undirect graph. Am I wrong?
So what ...
- 111
4
votes
2
answers
96
views
Is there a name for the problem of turning a bipartite graph into two graphs?
Is there a name for the problem of turning a bipartite graph into two graphs in the following way? We form one graph from the vertices on the left, such that two vertices are made adjacent if they ...
- 195
1
vote
0
answers
97
views
Choosing edges to disconnect graph
I have an undirected simple graph and an integer x.
My goal is to remove x edges from the graph so the largest connected component of the graph after the removal will be minimal.
I tried to think how ...
- 11
1
vote
1
answer
192
views
Optimal data structure for a time-windowed streaming graph in order to compute fast statistics
I apologize if this is the wrong place or too trivial a question for this community. What is the best data structure to store a time-windowed streaming graph in order to compute fast statistics over ...
- 11
7
votes
2
answers
220
views
Has this model of random directed graphs been studied?
Youtube recently added a feature called autoplay, where each clip is assigned a (presumably related) clip that follows it. This, in effect, defines a directed graph on the set of youtube clips, where ...
- 359
7
votes
0
answers
218
views
Computing the "at least k friends in common" graph
Suppose we have the graph of a social network with symmetric connections (e.g. Facebook or LinkedIn). Suppose we would like to find all pairs of people who have at least k friends in common, in order ...
- 2,269
0
votes
1
answer
141
views
How do I see SSL/TLS packet data in clear? [closed]
Hey all I have a weird question (first time poster so forgive me if this is super newb)...
I am wanting to see the inner workings of a SSL/TLS connection between a client and a server at the packet ...
-1
votes
1
answer
92
views
Probabilistic Analysis in real time network : Error in data and feedback channel. Two users communication
I'm studying probabilistic analysis in real time network. We have learned how many attempts in average are required to transmit a packet when there is no error on the feedback channel.
With no error ...
3
votes
1
answer
400
views
How do we know to what community a vertex belongs to in the Girvan-Newman algorithm?
So I've been doing some reading on community detection in graphs as I'm planning on working on my thesis for it. I've been reviewing papers regarding the same and came across the Girvan-Newman ...
- 314