Questions tagged [network-modeling]
The network-modeling tag has no usage guidance.
35
questions
1
vote
1
answer
82
views
Algorithm for Shortest Path in a DAG with Multiple Transportation Modes and Associated Setup Costs
I am working on a problem involving finding the shortest path in a Directed Acyclic Graph (DAG), where each edge's cost depends on multiple transportation modes, each with its own setup cost. I am ...
1
vote
0
answers
74
views
Algorithmic game theory with decentralized mechanism of exchanging information
An interesting topic that I want to understand has to do with the decentralized exchange of information among a network of agents, however there is not a specific theory to make such a mathematical ...
6
votes
0
answers
455
views
Fastest exact algorithm for MAXCUT
Is the algorithm introduced in the following paper still the fastest exact algorithm for general MAXCUT problems? TIA
Ryan Williams, A new algorithm for optimal $2$-constraint satisfaction and its ...
1
vote
1
answer
73
views
Bipartite graph projections, with threshold
Let $G=(\top,\bot,E)$ be a bipartite graph: $E\subseteq \top\times\bot$.
The projections $G_\bot = (\bot,E_\bot)$ and $G_\top = (\top,E_\top)$ of $G$ are defined as follows: two vertices are linked ...
3
votes
1
answer
474
views
A stronger Flow Decomposition Theorem?
In the classic Network Flows: Theory, Algorithms, and Applications book (pages 80/81) the flow decomposition theorem is stated as follows:
Every nonnegative arc flow x can be represented as a path ...
1
vote
0
answers
172
views
Network Reliability Problem
Network reliability, in which we are given an undirected graph $G$ with a failure probability $p_e$ for each edge and we are asked to calculate the probability that the network becomes disconnected ...
1
vote
0
answers
118
views
Shortest s-t Path with a covering constraint
Instance: an undirected graph $G=(V,E)$ with edge-weights $w:E\to{\mathbb{R}}$;
a source $s\in V$ and a sink $t\in V$;
a ground set $X=\{x_1, ..., x_k\}$, and for every $v\in V$ a corresponding ...
2
votes
0
answers
94
views
Which computational framework lies behind the Chinese “Social Credit System”?
BACKGROUND
The Social Credit System is a data-driven reputation system which draws on several sources to label various entities, namely businesses and individual citizens, with a trustworthiness ...
0
votes
1
answer
47
views
Does fixed hyperparameters perform well regardless the number of training examples?
I'm new in this community and I don't know whether my question is proper for this community. I will delete this post if it is not proper.
I'm interested in deep learning network models and have a ...
1
vote
1
answer
230
views
Total flow using minimum number of edges on a bipartite network
If I have a set of sources $S$ with total capacity $C$ and a set of sinks $T$ with the same capacity $C$, but not necessarily the same cardinality, is there an efficient way to find the minimum number ...
1
vote
0
answers
75
views
limit the total flow for some edges in an directed graph
How can I limit the total flow for some edges in an directed graph. We know that every edge can have an upper and lower bound solely. But apart from this sole upper and lower bounds for each edge, if ...
0
votes
1
answer
2k
views
What is "Synthetic Network" in Network Science?
I checked out several articles, books available, but didn't find what exactly is a "synthetic network".
3
votes
1
answer
166
views
Does such model exists?
I have a problem on distributed graph, with the following model:
1. There is a Global Graph $G=(V,E)$
2. There are $k$ computers.
3. Each computer $1 \leq i \leq k$ knows ALL the nodes of the graph,...
5
votes
1
answer
117
views
Survivable networks, directed case
I have been working on a project that turns out to be a special case of the directed version of the survivable network problem.
Iterative rounding gives a 2-approximation of the undirected case. I'm ...
2
votes
0
answers
45
views
centralized deterministic Spanner construction with low degree and low stretch
Does there exist a centralized deterministic spanner construction with low degree and low stretch both independent of the graph diameter (no log D factor), but can be dependent on the number of nodes. ...
2
votes
0
answers
69
views
An Exact Cover Variant encoded in a 4-Terminal Network
During research, I hit the following problem
Exact Cover Variant (ECV)
Input: Three set systems $S_1, S_2, S_3$ over a universe $U$, each closed with respect to $\cap$ and $\cup$.
Question: Is there ...
1
vote
1
answer
82
views
What does the contention-free communication assumption really mean in the context of DAG scheduling?
In many papers about DAG (directed-acyclic graph) scheduling in distributed systems, the authors make the assumption that the communication between the processors of the system where the DAG is ...
2
votes
0
answers
103
views
What mathematical models can analyze and optimize such message passing system?
I look for a mathematical model that can accommodate, analyze and suggest optimizations for a system that can be humanly described as message passing black box programs to which where optimal message ...
4
votes
1
answer
681
views
Bipartite scale-free networks
The Barabasi-Albert model describes a mechanism of generating random scale-free networks:
Growth: Starting with a small number ($m_0$) of connected nodes, at every time step, we add a new node with $...
3
votes
0
answers
370
views
Bipartite small-world networks
The Watts-Strogatz model describes a mechanism of generating small-world networks.
The idea is to start from a ring network in which each node is connected a fixed number of its closest neighbors. ...
2
votes
0
answers
165
views
Decomposing Graph Flow (Solution exists?)
I'm wondering if someone can point me towards understanding this problem better. Suppose I have the graph $G = \{V,E\}$ with vertices $v \in V$ and directed edges $e_{i,j} \in E$. Each node has an "in-...
3
votes
1
answer
650
views
How do you initialize your seed in the preferential attachment model?
Suppose that we seed our network with $m$ vertices. Suppose that at each step we add a vertex and c edges adjacent to that vertex.
Should these initial $m$ vertices have no edges at the start of the ...
7
votes
1
answer
151
views
Is it possible to create a machine learning classifier to generate Mock interfaces for systems testing?
I'm investigating whether it is feasible to be able to learn a system interface by watching network traffic (assuming the usual problems are solved e.g. encryption etc)
I haven't been able to find ...
4
votes
2
answers
363
views
Algorithms for creating a directed network with a given 3-node motifs distribution
I am looking for algorithms to create directed networks with an arbitrary distribution of 3-node network motifs (i.e. subgraphs of the order 3), see this picture from O. Sporns, R. Kotter, Motifs in ...
1
vote
1
answer
614
views
Theoretical proof of convergence of sequential weight update procedure (Neural Networks and Machine Learning)
My question is at the bottom.
(Most of the descriptive words come from Chris. Bishop's Neural Networks for Pattern Recognition)
let $w$ be the weight vector of the neural network and $E$ the error ...
1
vote
0
answers
69
views
Strategies for preventing isolated nodes in a dynamically changing undirected cyclic graph
I'm building a mesh network where i need to detect the unexpected disappearance of a peer.
Each node attempts to stay in communication with at least X peers. A node refuses connection from another ...
-2
votes
1
answer
133
views
How to check if an algorithm in a distributed system worked within restraints?
I want to design a system in which a program is sent along with data and then it answers with the result. Is redundancy a must in this situation to check for correctness of the processed data? What is ...
7
votes
1
answer
136
views
Complexity of selective network improvement problem
We have a network flow problem with a given directed graph $G=(V,E)$, for each arc $(i,j) \in E$, there is a cost $c_{ij}$ and upper and lower capacity $u_{ij}$ and $l_{ij}$ for the flow $f_{ij}$ ...
4
votes
1
answer
261
views
Laying paths on a network using minimum number of links/edges
Consider an undirected graph G(V,E), where each edge $e\in E$ has capacity $c(e)$. Also given is a traffic matrix $T_{ij}$ representing the amount of traffic flowing from vertex $i$ to $j$. The goal ...
1
vote
0
answers
285
views
Using Graphs/Graph Similarity as Features for a Learner
I'm working to construct a learner than can recognize whether two vertices in a property graph (digraph, vertices and edges can have arbitrary keys/values) modelling a social network in fact represent ...
4
votes
1
answer
175
views
Given a network flow, are there bounds on the change in weight on nodes?
Here's my precise situation: I have a graph with nodes $V$ and edges $E$, and the nodes have some non-negative integer weights $w_i$. In one step of the protocol, I am now allowed to move weight ...
1
vote
0
answers
141
views
Structured Graph Generation
I hope you can help. I am looking for the best way to generate random bipartite graphs with localised structure within one of the node types. Such that type A visits a local group of type B with a ...
15
votes
3
answers
928
views
Super Mario Flows in NP?
One classical extension of the max-flow problem is the "max-flow over time" problem: you are given a digraph, two nodes of which are distinguished as the source and the sink, where each arc has two ...
4
votes
1
answer
8k
views
Queueing Theory: How to estimate steady-state queue length for single queue, N servers?
I have a real-life situation that can be solved using Queueing Theory.
This should be easy for someone in the field. Any pointers would be appreciated.
Scenario:
There is a single Queue and N ...
4
votes
3
answers
353
views
How can I model this usage scenario mathematically?
I want to create a fairly simple mathematical model that describes usage patterns and performance trade-offs in a system.
The system behaves as follows:
clients periodically issue multi-cast packets ...